Modeling Discrete Data with High-Order Vector Potts Models Aaron De Clercq, Merijn Moody, Clélia de Mulatier Abstract Modeling high-dimensional data is challenging, yet essential to understanding many complex systems. Maximum entropy models such as Ising and Potts models have been used extensively to capture pairwise interactions from correlation patterns in data, allowing to infer graphical representations of complex systems from observations (e.g., from protein sequences, or neural population activity). Recently, there has been growing interest in modeling higher-order correlation patterns involving simultaneously three or more variables. While progress has been made in binary data with high-order Ising models, we extend this framework to the more general case of discrete data. We introduce q q -state spin models, a complete family of maximum entropy models that generalize the vector Potts model to include long-range and arbitrary high-order interactions. Even in the pairwise case, compared to the standard vector Potts model, our models allow for more diverse interaction types. We discuss their statistical interpretation through examples and relate these models to discrete Fourier analysis. Using a loop expansion of the partition function, we show that the statistical properties of q q -state spin models are fully captured by the algebraic structure of their interactions. We define gauge transformations under which this structure, and therefore the partition function, remains invariant. Models equivalent under gauge transformations can thus be seen as different representations of the same abstract statistical model, despite potentially having interactions of different orders, extending results from the binary case. For practical application of this framework to data analysis, we focus on a subset of models known, in the binary case, as Minimally Complex Models, generalizing them to discrete data. We obtain a closed-form expression for the marginal likelihood of these models, enabling fast model selection. We illustrate their use with simple real-world examples. Keywords statistical inference \cdot discrete data \cdot Potts model \cdot high-order interactions \cdot gauge transformation \cdot cluster expansion \cdot information theory \cdot complexity 1 Introduction The analysis of high-dimensional data has become a central challenge in modern science, driven by the explosion of high-throughput experiments. Whether analyzing the firing patterns of neural populations, the sequence variations in protein families, or gene regulatory networks, the primary goal is often the same: to infer the microscopic laws or structural constraints governing the system based on macroscopic observations obtained from experimental data. From a statistical modeling standpoint, this problem is frequently addressed using the principle of maximum entropy 25 , which enables the construction of the least biased probability distribution consistent with measured observables. Over the last three decades, this approach has been successful at reconstructing graphical models of microscopic interactions in complex systems from discrete data, specifically pairwise Ising and Potts models. More generally, physicists have reformulated the task of extracting information from large, high-dimensional data as an inverse statistical problem 39 . This research has found broad application across the biological sciences, such as the reconstruction of neural functional connectivity from population activity 48 ; 13 , the inference of gene regulatory networks from sequencing data 33 , and the determination of three-dimensional protein structures from sequence variations 53 ; 35 ; 17 ; 6 ; 24 ; 46 . Many complex systems however have high-order interactions between their components, which are simultaneous interactions between three or more components, and can exhibit behaviors that are not well explained by pairwise models. In data, this can appear for instance as high-order correlation patterns between the states of the components (i.e., correlations between three or more variables) that cannot be explained by the pairwise correlation structure of the data. This general problem has led to a recent surge of interest for models with high-order interactions in many fields of complex systems 8 ; 7 . From a data modeling perspective, finding which high-order interactions are most relevant to explain the data (if any) is particularly challenging due to the combinatorial explosion of the number of possible interactions. Recent progress has been made in addressing this challenge for binary data . To model high-order statistical patterns, References 34 ; 9 proposed a generalization of Ising-like maximum entropy models to include interactions of arbitrarily high order, which the authors generally call “spin models” (also known in the literature as “high-order Ising models” or “generalized Ising models” 52 ). Consider a binary dataset composed of multiple observations of the state \boldsymbol{s}=(s_{1},\,\cdots,\,s_{n}) of n binary variables s_{i} taking values in \{-1,+1\} (called “spin” variables). A spin model is a parametric family of probability distributions of the form 9 : p(\boldsymbol{s}\,|\,\boldsymbol{g},\mathcal{M})=\frac{1}{Z_{\mathcal{M}}(\boldsymbol{g})}\,\exp\left({\;\sum_{\boldsymbol{\mu}\in\mathcal{M}}g_{\boldsymbol{\mu}}\,\phi^{\boldsymbol{\mu}}(\boldsymbol{s})}\right)\,, (1) characterized by the choice of a set \mathcal{M}=\{\boldsymbol{\mu}^{(1)},\,\ldots,\boldsymbol{\mu}^{(K)}\} of K interactions of arbitrary order between the spins. Each interaction is represented by an n -dimensional binary vector \boldsymbol{\mu} that indicates which spins are interacting, and the functions \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) define how the variables interact, taking the form of product operators: \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=\prod_{i=1}^{n}{s_{i}}^{\mu_{i}}\,,\qquad\forall\boldsymbol{\mu}\in(\mathbb{Z}/2\mathbb{Z})^{n}\,. (2) For example, in a five-spin system, a three-body interaction between s_{1} , s_{3} and s_{4} is represented by the binary vector \boldsymbol{\mu}=(1,0,1,1,0) and corresponds to the operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=s_{1}s_{3}s_{4} . Ising-like (pairwise) models only have operators of the form \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=s_{i} and \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=s_{i}s_{j} between pairs of spins. The vector \boldsymbol{g}=(g_{\boldsymbol{\mu}})_{\boldsymbol{\mu}\in\mathcal{M}} is a vector of real parameters, and the normalization factor Z_{\mathcal{M}}(\boldsymbol{g}) , known in physics as the partition function of the model, is given by: \displaystyle Z_{\mathcal{M}}(\boldsymbol{g})=\sum_{\boldsymbol{s}}\,\exp\left({\;\sum_{\boldsymbol{\mu}\in\mathcal{M}}g_{\boldsymbol{\mu}}\,\phi^{\boldsymbol{\mu}}(\boldsymbol{s})}\right)\,. (3) The spin models ( 1 ) are maximum entropy models constrained to produce chosen expectation values of the operators in \mathcal{M} . These values correspond to (high-order) moments of the multivariate systems that are considered as the relevant macroscopic observables by the model. The coefficients g_{\boldsymbol{\mu}} are Lagrange multipliers, which are usually fitted so that the model average \langle\phi^{\boldsymbol{\mu}}\rangle=\sum_{\boldsymbol{s}}p(\boldsymbol{s}\,|\,\boldsymbol{g},\mathcal{M})\,\phi^{\boldsymbol{\mu}}(\boldsymbol{s}) of each operator in \mathcal{M} matches its empirical average in the data. The family of spin models is thus able to capture any possible patterns of binary data (i.e., any choice of the multivariate moments). In particular, the complete model with all (2^{n}-1) interactions can fit all high-order correlation patterns. In this context, identifying which patterns of the data are relevant is equivalent to finding the subset of interactions that best models the data, which is challenging due to the super-exponential number of possible choices. An interesting property of this family of models, with important implications for modeling, is that it is closed under changes of representation of the spin variables, called gauge transformations by 9 . A gauge transformation is a bijective map of the form \boldsymbol{\sigma}=\boldsymbol{b}(\boldsymbol{s}) , which defines a new basis of spin variables \boldsymbol{\sigma}=(\sigma_{1},\cdots,\sigma_{n}) in terms of the original variables \boldsymbol{s} using a set of independent operators \boldsymbol{b}(\boldsymbol{s})=(\phi^{\boldsymbol{\mu}_{1}}(\boldsymbol{s}),\dots,\phi^{\boldsymbol{\mu}_{n}}(\boldsymbol{s})) (see example in Fig. 1 ). The probability distribution ( 1 ) of any spin model can be rewritten in the new basis \boldsymbol{\sigma} by re-expressing each spin operator in terms of the new variables. In the new basis, the operators still have the form of spin operators, and the model probability distribution thus remains that of a spin model 1 1 1 Under a gauge transformation, any spin operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) can be transformed by re-expressing it in terms of the new basis variables \boldsymbol{s}^{\prime}=\boldsymbol{b}(\boldsymbol{s}) . Using the inverse transformation \boldsymbol{s}=\boldsymbol{b}^{-1}(\boldsymbol{s}^{\prime}) , the transformed operator is given by: \mathcal{T}_{\boldsymbol{b}}[\phi^{\boldsymbol{\mu}}](\boldsymbol{s}^{\prime})\doteq\phi^{\boldsymbol{\mu}}(\boldsymbol{b}^{-1}(\boldsymbol{s}^{\prime}))\,. (4) This yields a transformed model \mathcal{T}_{b}[\mathcal{M}] , which is obtained by transforming each operator within \mathcal{M} : \mathcal{T}_{\boldsymbol{b}}[\mathcal{M}]\doteq\{\mathcal{T}_{\boldsymbol{b}}[\phi^{\boldsymbol{\mu}}]\mid\phi^{\boldsymbol{\mu}}\in\mathcal{M}\}\,. (5) Consequently, the probability of finding the system in state \boldsymbol{s} under model \mathcal{M} is identical to the probability of finding the system in the transformed state \boldsymbol{s}^{\prime} under the transformed model \mathcal{T}_{\boldsymbol{b}}[\mathcal{M}] : p(\boldsymbol{s}\,|\,\boldsymbol{g},\mathcal{M})=p(\boldsymbol{s}^{\prime}\,|\,\boldsymbol{g}^{\prime},\mathcal{T}_{\boldsymbol{b}}[\mathcal{M}])\,, (6) where the parameter vector \boldsymbol{g}^{\prime} is a permutation of the original parameters \boldsymbol{g} , ensuring that the transformed operator in \mathcal{T}_{\boldsymbol{b}}[\mathcal{M}] is coupled to the same parameter as the original operator in \mathcal{M} . 9 . We denote \mathcal{M}^{\prime}=\mathcal{T}_{\boldsymbol{b}}[\mathcal{M}] the spin model resulting from the gauge transformation \boldsymbol{\sigma}=\boldsymbol{b}(\boldsymbol{s}) of a model \mathcal{M} . Crucially, models related by a gauge transformation can have interactions of different orders. In particular, standard pairwise models can map to models containing high-order interactions. Moreover, models related by gauge transformations have the same partition function Z_{\mathcal{M}}(\boldsymbol{g}) 9 , and can thus be understood as different representations of the same abstract statistical model. This gives rise to the concept of equivariant model selection , as illustrated in Figure 1 . Suppose we have a binary dataset \boldsymbol{\hat{s}} written in terms of the variables \boldsymbol{s} (Bob’s dataset) and our model selection procedure yields an optimal model \mathcal{M} . If we rewrite the dataset in terms of the new basis variables \boldsymbol{\sigma}=\boldsymbol{b}(\boldsymbol{s}) using a gauge transformation and perform the exact same model selection procedure to the new dataset \boldsymbol{\hat{\sigma}} (Alice’s dataset), it will yield a model \mathcal{M}^{\prime} that is a priori different from \mathcal{M} . One can expect an unbiased model selection procedure among all spin models to yield models that are consistent across different representations of the data. In this example, this would mean that \mathcal{M}^{\prime} is related to \mathcal{M} by the same gauge transformation, \mathcal{M}^{\prime}=\mathcal{T}_{\boldsymbol{b}}[\mathcal{M}] . Such a model selection procedure is called equivariant. Because the family of pairwise models is not closed under gauge transformations, equivariant model selection is fundamentally impossible unless we encompass high-order interactions within our model selection framework. This underscores the importance of developing a comprehensive high-order framework for statistical inference. Figure 1: Example illustrating equivariant model selection for binary datasets \boldsymbol{\hat{s}}=\{\boldsymbol{s}^{(i)}\}_{i=1}^{N} , where each datapoint \boldsymbol{s}^{(i)} is a state of a three-spin system \boldsymbol{s}=(s_{1},s_{2},s_{3})\in\{-1,+1\}^{3} . A model selection procedure is equivariant if, for a basis transformation of the dataset \mathcal{T}\colon\boldsymbol{s}\to\boldsymbol{\sigma} , the models obtained from the model selection procedure on \boldsymbol{\hat{s}} (Bob’s data) and \boldsymbol{\hat{\sigma}} (Alice’s data) are related by the same transformation \mathcal{T} . The left panel shows an example of an equivariant model selection procedure, for which the spin model found in Alice’s data representation corresponds to the model found in Bob’s representation rewritten in Alice’s basis, i.e. \mathcal{M}_{\rm Alice}=\mathcal{T}[\mathcal{M}_{\rm Bob}] . In the right panel, Alice and Bob have the same data as in the left panel, but they can only select among pairwise models. In this case, Bob will find the same model as in the left panel because his model is already pairwise, but Alice’s model cannot be the same because her model has a three body interaction. Instead, Alice will find a pairwise model that likely has similarities with her left-panel model (such as the projection of the three-body interaction onto pairwise interactions), but which cannot be consistent with Bob’s findings anymore. This gives an example where it is clear that pairwise model selection is not equivariant. While this framework is well-established for binary variables, a comprehensive framework for discrete data (where variables can take q different values with q\geq 2 ) remains under-explored. In this paper, we extend this framework to the more general case of discrete data. Taking inspiration from the binary case, we define a complete family of maximum entropy models able to reproduce arbitrary multivariate moments of the discrete data. This family of models, which we call q -state spin models, generalizes the vector Potts model to include arbitrary high-order interactions, and reduces to the models in ( 1 ) when q=2 . The complete q -state spin models, with all 2^{q^{n}-1} parameters, can model any patterns of discrete data. More specifically, we can relate this model to a Fourier decomposition of the log-probability. Similarly to the binary case, we identified changes of representation of the discrete system (gauge transformations) that transform a q -state spin model into another q -state spin model, with interactions that can be of different orders. Using a loop expansion of the partition function, we show that these models have the same partition function, and thus correspond to different representations of the same abstract statistical model. This defines equivalent classes of q -state spin models, which, in particular, allows for the development of equivariant model selection. We introduce a linear algebra representation of spin models, which provides a comprehensive mathematical framework for working with spin models. In particular, this framework formalizes the definition of gauge transformations, the characterization of the loop structure and of equivalence classes, and the definition of symmetries in data and models. While the complete model can be used to infer all probability distributions, it is generally over-parameterized for modeling systems with limited data. The challenge of finding a good model for data lies in selecting the most concise description that captures the relevant statistics without overfitting. Ideally, one would compare all possible models to find the one that best describes a dataset \boldsymbol{\hat{s}}=\{\boldsymbol{s}^{(i)}\}_{i=1}^{N} , i.e., the one achieving an optimal balance between goodness-of-fit and simplicity. Assuming no prior preference between models, we aim to find the model with the largest evidence (or marginal likelihood ) 31 : P(\boldsymbol{\hat{s}}\,|\,\mathcal{M})=\int_{\mathbb{R}^{M}}\!d\boldsymbol{g}\,\prod_{i=1}^{N}\,p\big(\boldsymbol{s}^{(i)}|\,\boldsymbol{g},\mathcal{M}\big)\;P_{0}(\boldsymbol{g}\,|\,\mathcal{M})\,, (7) where P_{0}(\boldsymbol{g}\,|\,\mathcal{M}) is a prior distribution over the model parameters. Assuming Jeffreys’ prior, in the limit of a large number N of datapoints, maximizing the evidence is also equivalent to finding the model minimizing the description length of the data 44 ; 43 ; 21 ; 5 ; 38 : \displaystyle L(\boldsymbol{\hat{s}}\,|\,\mathcal{M})=\max_{\boldsymbol{g}}\log P(\boldsymbol{\hat{s}}\,|\,\boldsymbol{g},\,\mathcal{M})-\frac{K}{2}\,\log\left(\frac{N}{2\pi}\right)-c_{\mathcal{M}}+O\left(\frac{1}{N}\right)\,. (8) The first term measures goodness-of-fit of the model, while the subsequent terms penalize model complexity, based on the number K of parameters and the geometric complexity c_{\mathcal{M}} 38 ; 9 . Calculating these quantities for all possible models is computationally intractable. To remedy this, we generalize the definition of minimally complex models (MCMs), introduced for binary data in Ref. 15 , to the discrete case. MCMs are a sub-family of the q -state spin models that correspond to factorizations of the model probability distribution in some spin basis. A remarkable advantage of MCMs is that the model evidence ( 7 ) has a closed-form expression, making Bayesian model selection among MCMs feasible. The MCM with the largest evidence then identifies an optimal factorization of the empirical probability distribution that matches the data structure. The paper is organized as follows. In Section 2 , we define high-order vector Potts models, as maximum entropy models constrained to reproduce high-order moments of a discrete spin system. In Section 3 , we obtain a loop expansion of the partition function, which connects the statistical properties of the model to its algebraic structure (the loops of the model), extending results from the binary case to general q . In Section 4 , we introduce a linear algebra representation of spin models, which gives a formal framework for working with equivalence classes of q -state spin models. Finally, in Section 5 , we focus on the subset of Minimally Complex Models and, in Section 6 , we illustrate their use for model selection in real-world discrete data. 2 Complete family of maximum entropy models for discrete data In this section, we define a complete family of parametric models for discrete data. Inspired by the high-order generalization of the Ising model in Eq. ( 1 ) 34 ; 9 , we define maximum entropy models able to reproduce any (high-order) moments of a discrete planar spin system, introducing a high-order generalization of the planar Potts model ( 41 ) for statistical inference of discrete data. The resulting family of probability distributions extends the maximum entropy models in Eq. ( 1 ) to any discrete values of q\geq 2 . In Sec. 2.3 , we draw attention to the fact that these models correspond to a spatial discrete Fourier decomposition of the empirical log-probability (or energy function), which has interesting implications regarding the use of these models. Finally in Sec. 2.4 , we give some insight into the way these models encode patterns of discrete data. 2.1 Definitions – q -state spin models with interactions of arbitrary order We are interested in studying systems of n random variables that can take q different values (where q is a positive integer). One can map these q values to integers between 0 and (q-1) without losing in generality. We consider discrete variables in this format and define planar spin variables by mapping these q values to evenly spaced positions on the unit circle. The choice of this initial mapping must be taken into account when interpreting the interactions of the model, which will be discussed in Sec. 2.4 . Definition 1 . Discrete variables: q -state spins and colors. Consider n discrete random variables (\alpha_{1},\,\cdots,\,\alpha_{n}) taking integer values in [0,\,q-1] : \displaystyle{\rm for}\;{\rm all}\;j\in\{1,\cdots,n\},\qquad\alpha_{j}\in(\mathbb{Z}/q\mathbb{Z})\,. (9) This system can be mapped to the system of n complex variables (s_{1},\,\cdots,s_{n}) taking values in the set of the q -th roots of unity, using: \displaystyle{\rm for}\;{\rm all}\;j\in\{1,\cdots,n\},\qquad\qquad s_{j}=\exp\left({\displaystyle\frac{2i\pi}{q}\alpha_{j}}\right)=z_{q}^{\;\alpha_{j}}\,, (10) where z_{q}=\exp(\frac{2\pi}{q}\,i) is the first q -th root of unity. We refer to the variables s_{j} as q -state spin variables and to the variables \alpha_{j} as their colors . Figure 2: Representation for q -state spin variables in the complex plane for different values of q . For a given value of q , the color variable \alpha_{i} can take any integer value modulo q , \alpha_{i}\in(\mathbb{Z}/q\mathbb{Z})^{n} . The corresponding q -state spin variable then takes the complex value s_{i}=z_{q}^{\,\alpha_{i}} , where z_{q} is the first q -th root of unity. The spin variable can thus be represented in the complex plane by a random unit vector which can point in any of the q different directions corresponding to the q -th roots of unity. Observe that z_{q}^{q-\alpha_{i}} and z_{q}^{\,\alpha_{i}} are complex conjugate spin values, z_{q}^{q-\alpha_{i}}=(z_{q}^{\,\alpha_{i}})^{*} , which correspond to mirrored directions of s_{i} with respect to the x -axis. Equation ( 10 ) defines a bijection between the two sets of random variables. In the complex plane, the spin variable s_{j} can be seen as a random unit vector whose direction is given by the color variable \alpha_{j} (see Fig. 2 ), similarly to the planar spins introduced in the very first version of the Potts model ( 41 ) . We denote the state of the system by the vector \boldsymbol{\alpha}=(\alpha_{1},\,\cdots,\alpha_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} when expressed in terms of the variables \alpha_{j} and by the complex vector \boldsymbol{s}=(s_{1},\,\cdots,s_{n}) when expressed in terms of the variables s_{j} . In the following, we will use interchangeably the notation with dependency in \boldsymbol{s} or in \boldsymbol{\alpha} . For q=2 , the variables s_{j} can take the values +1 (for \alpha_{j}=0 ) or -1 (for \alpha_{j}=1 ), just like in the Ising model and its high-order generalization ( 1 ). One reason for introducing the spin variables s_{j} in the form of ( 10 ) is that they satisfy the property s_{j}^{\,q}=1 . In the binary case, this property is useful for defining gauge transformations and to obtain a loop expansion of the partition function 9 , both of which we aim to generalize here. Below, this property is also useful for defining a complete set of high-order moments from which a complete family of maximum entropy model can constructed. 2.1.1 High-order moments, spin operators, and complete models We aim to define a complete family of parametric models, able to capture any pattern of discrete data. This can be done by defining maximum entropy models constrained to reproduce any choice of moments of the observed system (including high-order moments). In the following, we construct a family of maximum entropy models able to reproduce arbitrary-order moments of the spin variables s_{j} , as opposed to moments of the colors \alpha_{j} . Definition 2 . Moments of an n -spin system. For the system of n q -state spin variables s_{j} , there are at most (q^{n}-1) possible distinct moments, each corresponding to a product of the spins raised to some power between 0 and (q-1) : \displaystyle\bigg\langle\,\prod_{j=1}^{n}\,s_{j}^{\;\mu_{j}}\,\bigg\rangle\,,\qquad\textrm{for all integer values of }\;\mu_{j}\in(\mathbb{Z}/q\mathbb{Z})\,, (11) except (\mu_{1},\,\cdots,\,\mu_{n})=\boldsymbol{0}\, for which the product is simply equal to 1 . The angle brackets \langle\,\cdot\,\rangle denotes the ensemble average. Because the spin variables defined in Eq. ( 10 ) verify 2 2 2 For all \mu_{j}\geq q\, , \;s_{j}^{\mu_{j}}=\exp\left({\frac{2i\pi}{q}\alpha_{j}\mu_{j}}\right)=\exp\left({\frac{2i\pi}{q}\alpha_{j}(\mu_{j}\bmod{q})}\right)=s_{j}^{\mu_{j}\bmod{q}}\, . that s_{j}^{\mu_{j}}=s_{j}^{\mu_{j}\bmod{q}} , all the moments corresponding to values of \mu_{j}\geq q are equal to lower order moments of the form of Eq. ( 11 ), and therefore there are at most (q^{n}-1) possible distinct moments. These moments define a complete set of patterns of discrete data, i.e., they can fully describe any possible statistical structure of discrete data. We introduce the n -dimensional vector \boldsymbol{\mu}=(\mu_{1},\,\cdots,\,\mu_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} , such that each value of \boldsymbol{\mu} uniquely identifies one of the moments in Eq. ( 11 ) (except for \boldsymbol{\mu}=\boldsymbol{0} ). The maximum entropy model 25 ; 50 constrained to reproduce all these moments then takes the form: \displaystyle p(\boldsymbol{s}\,|\,\boldsymbol{g})=\frac{1}{Z(\boldsymbol{g})}\,\exp\Bigg({\;\sum_{\vecmu\in[\Field^n]^*} g_{\vecmu}\,\phi^{\vecmu}(\spin)}\Bigg)\,, (12) where the sum is over all \boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n} except \boldsymbol{\mu}=\boldsymbol{0} (indicated by the star), Z(\boldsymbol{g}) is a normalization factor corresponding to the partition function of the model, the g_{\boldsymbol{\mu}} ’s are (q^{n}-1) complex parameters corresponding to Lagrange multipliers ( \boldsymbol{g} is the vector of all the parameters g_{\boldsymbol{\mu}} ), and the \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) ’s are the spin operators associated to each of the moments in Eq. ( 11 ) defined as follow. Definition 3 . (Complex) Spin operators of arbitrary order. For all states \boldsymbol{s} of the n -spin system and all vectors \boldsymbol{\mu}=(\mu_{1},\cdots,\mu_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} , we define the spin operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) as the monomial: \displaystyle\phi^{\boldsymbol{\mu}}(\boldsymbol{s})=\prod_{j=1}^{n}s_{j}^{\;\mu_{j}}\,. (13) For binary systems ( q=2 ), the exponents \mu_{j} ’s can only take the values 0 or 1 , and we recover the Ising spin operators defined in Eq. ( 2 ) 34 ; 9 . Using Eq. ( 10 ), the spin operators can also be written in term of the color variables \boldsymbol{\alpha}=(\alpha_{1},\cdots,\alpha_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} : \displaystyle\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=\exp\left(\sum_{j=1}^{n}{\displaystyle\frac{2i\pi}{q}\alpha_{j}\mu_{j}}\right)=\exp\left({\displaystyle\frac{2i\pi}{q}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}}\right)=z_{q}^{\;\boldsymbol{\mu}\cdot\boldsymbol{\alpha}}\,, (14) where \boldsymbol{\alpha}\cdot\boldsymbol{\mu} is the scalar product of \boldsymbol{\alpha} and \boldsymbol{\mu} in (\mathbb{Z}/q\mathbb{Z})^{n} . Note that for q=2 , \,\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=(-1)^{\boldsymbol{\alpha}\cdot\boldsymbol{\mu}}\in\{\pm 1\} . The ensemble averages of the spin operators in Eq. ( 13 ) define all the moments of the spin system ( 11 ) (except for the operator \phi^{\boldsymbol{0}}(\boldsymbol{s})=1 ). Thus, at best fit of the maximum entropy model ( 12 ), the values taken by these moments in the model are precisely equal to their values in the data, because these are the patterns the model was constrained to reproduce 25 ; 50 . One caveat of the model in Eq. ( 12 ) is that the term in the exponential can take complex values (as both g_{\boldsymbol{\mu}} and \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) can be complex), and therefore the state probabilities p(\boldsymbol{s}\,|\,\boldsymbol{g}) can be complex. Observe however that for each complex operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) , there is another operator \phi^{-\boldsymbol{\mu}}(\boldsymbol{s})=[\phi^{\boldsymbol{\mu}}(\boldsymbol{s})]^{*} that is equal to its complex conjugate 3 3 3 \phi^{-\boldsymbol{\mu}}(\boldsymbol{s})=[\phi^{\boldsymbol{\mu}}(\boldsymbol{s})]^{*} because s_{j}^{-\mu_{j}}=\exp\left(-{\frac{2i\pi}{q}\alpha_{j}\mu_{j}}\right)=[\exp({\frac{2i\pi}{q}\alpha_j\mu_j})]^{*}=\big[s_{j}^{\,\mu_{j}}\big]^{*} for all \mu_{j}\in(\mathbb{Z}/q\mathbb{Z}) . in the model ( 12 ). These operators correspond to the vectors \boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n} such that -\boldsymbol{\mu}\neq\boldsymbol{\mu} , where -\boldsymbol{\mu} denotes 4 4 4 The vector -\boldsymbol{\mu} is defined in (\mathbb{Z}/q\mathbb{Z})^{n} by applying a “minus” sign to all the entries of \boldsymbol{\mu} and taking them modulo q . the vector -\boldsymbol{\mu}=(q-\mu_{1},\cdots, q-\mu_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} (for -\boldsymbol{\mu}=\boldsymbol{\mu} , the operators already take real values \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=\pm 1 ). In other words, the two operators \phi^{\boldsymbol{\mu}} and \phi^{-\boldsymbol{\mu}} impose similar constraints to the model. For the state probabilities p(\boldsymbol{s}\,|\,\boldsymbol{g}) to be real, we can then impose that: \displaystyle g_{-\boldsymbol{\mu}}=g_{\boldsymbol{\mu}}^{\,*}\,,\qquad\textrm{for all}\;\,\boldsymbol{\mu}=(\mu_{1},\,\cdots,\,\mu_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n}\,, (15) where g_{\boldsymbol{\mu}}^{*} is the complex conjugate of g_{\boldsymbol{\mu}} . Consequently, each pair of conjugate operators \phi^{\boldsymbol{\mu}} and \phi^{-\boldsymbol{\mu}} is only parameterized by two real parameters, a_{\boldsymbol{\mu}} and b_{\boldsymbol{\mu}} (instead of four), chosen below such that g_{\boldsymbol{\mu}}=(a_{\boldsymbol{\mu}}-ib_{\boldsymbol{\mu}})/2=g_{-\boldsymbol{\mu}}^{*} (see App. A.1 ). They constrain the model on reproducing respectively the real and the imaginary parts of \langle\phi^{\boldsymbol{\mu}}(\boldsymbol{s})\rangle . For values of \boldsymbol{\mu} such that -\boldsymbol{\mu}=\boldsymbol{\mu} , the operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s})\in\{\pm 1\} is real and Eq. ( 15 ) implies that g_{\boldsymbol{\mu}}=g_{\boldsymbol{\mu}}^{*} is also real. Equation ( 12 ) can thus be re-written under the form of a maximum entropy model constrained to reproduce the real and the imaginary part of all the moments ( 11 ) of a spin system: \displaystyle p(\boldsymbol{s}\,|\,\boldsymbol{g})=\frac{1}{Z(\boldsymbol{g})}\,\exp[\;\sum_{\begin{subarray}{c}\boldsymbol{\mu}\in[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*}\\ \boldsymbol{\mu}\leq-\boldsymbol{\mu}\end{subarray}}\left(a_{\boldsymbol{\mu}}\,\varphi^{\boldsymbol{\mu}}(\boldsymbol{s})+b_{\boldsymbol{\mu}}\,\psi^{\boldsymbol{\mu}}(\boldsymbol{s})\right)\Bigg]\,, (16) where the operators \varphi^{\boldsymbol{\mu}}(\boldsymbol{s})={\rm Re}[\phi^{\boldsymbol{\mu}}(\boldsymbol{s})] and \psi^{\boldsymbol{\mu}}(\boldsymbol{s})={\rm Im}[\phi^{\boldsymbol{\mu}}(\boldsymbol{s})] are respectively the real and imaginary parts of \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) (see Definition 4 – note that \psi^{\boldsymbol{\mu}}(\boldsymbol{s})=0 for all \boldsymbol{\mu} such that -\boldsymbol{\mu}=\boldsymbol{\mu} ). For all \boldsymbol{\mu} such that -\boldsymbol{\mu}\neq\boldsymbol{\mu} , contributions from conjugate operators have been grouped together as a_{\boldsymbol{\mu}}=g_{\boldsymbol{\mu}}+g_{-\boldsymbol{\mu}} and b_{\boldsymbol{\mu}}=i(g_{\boldsymbol{\mu}}-g_{-\boldsymbol{\mu}}) . For \boldsymbol{\mu} such that -\boldsymbol{\mu}=\boldsymbol{\mu} , we use the convention a_{\boldsymbol{\mu}}=g_{\boldsymbol{\mu}}=g_{\boldsymbol{\mu}}^{*} . The constraint \boldsymbol{\mu}\leq-\boldsymbol{\mu} ensures that the sum includes each conjugate pair (\boldsymbol{\mu},-\boldsymbol{\mu}) only once 5 5 5 The ordering between operators \boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n} is based on the ordering of the integers represented by \boldsymbol{\mu} in base q . . Here, the vector \boldsymbol{g} denotes the vector of real parameters a_{\boldsymbol{\mu}} and b_{\boldsymbol{\mu}} . In Eq. ( 16 ), it is clear that the state probabilities p(\boldsymbol{s}\,|\,\boldsymbol{g}) are now real. Definition 4 . (Real) Spin operators of arbitrary order. For all state \boldsymbol{s} of the n -spin system and all vector \boldsymbol{\mu}=(\mu_{1},\cdots,\mu_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} , we define the real spin operators \varphi^{\boldsymbol{\mu}}(\boldsymbol{s}) and \psi^{\boldsymbol{\mu}}(\boldsymbol{s}) as respectively the real and the imaginary parts of \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) : \displaystyle\varphi^{\boldsymbol{\mu}}(\boldsymbol{s})={\rm Re}[\phi^{\boldsymbol{\mu}}(\boldsymbol{s})]=\frac{\phi^{\boldsymbol{\mu}}(\boldsymbol{s})+\phi^{-\boldsymbol{\mu}}(\boldsymbol{s})}{2}\qquad{\rm and}\qquad\psi^{\boldsymbol{\mu}}(\boldsymbol{s})={\rm Im}[\phi^{\boldsymbol{\mu}}(\boldsymbol{s})]=\frac{\phi^{\boldsymbol{\mu}}(\boldsymbol{s})-\phi^{-\boldsymbol{\mu}}(\boldsymbol{s})}{2i}\,. (17) For all \boldsymbol{\mu} such that -\boldsymbol{\mu}=\boldsymbol{\mu} , \varphi^{\boldsymbol{\mu}}(\boldsymbol{s})=\phi^{\boldsymbol{\mu}}(\boldsymbol{s})\in\{\pm 1\} and \psi^{\boldsymbol{\mu}}(\boldsymbol{s})=0 . These operators can also be written in term of the discrete variables \boldsymbol{\alpha} as: \displaystyle\varphi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=\cos\left({\displaystyle\frac{2\pi}{q}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}}\right)\qquad{\rm and}\qquad\psi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=\sin\left({\displaystyle\frac{2\pi}{q}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}}\right)\,, (18) where \boldsymbol{\alpha}=(\alpha_{1},\cdots,\alpha_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} and \boldsymbol{\alpha}\cdot\boldsymbol{\mu} is the scalar product of \boldsymbol{\alpha} and \boldsymbol{\mu} in (\mathbb{Z}/q\mathbb{Z})^{n} . Number of real parameters. Requiring p(\boldsymbol{s}\,|\,\boldsymbol{g}) to be real reduces the effective number of real parameters in the model of Eq. ( 12 ). There are two real parameters, a_{\boldsymbol{\mu}} and b_{\boldsymbol{\mu}} , for each pair of conjugate operators and only one real parameter a_{\boldsymbol{\mu}} for each real operator (for which -\boldsymbol{\mu}=\boldsymbol{\mu} ). Therefore, the model has only (q^{n}-1) real parameters in total (equal to the number of non-zero vector \boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n} ). This is consistent with the number of parameters one would need to model the probability distribution by its (q^{n}-1) independent state probabilities (where the “ -1 ” comes from normalization). Because the model ( 12 ) (resp. ( 16 )) provides an alternative complete description of the discrete system, there exits a bijection between the (q^{n}-1) state probabilities and the (q^{n}-1) real parameters of the model. This means that for any distribution of the state probabilities 6 6 6 assuming that all the probabilities are strictly positive p(\boldsymbol{s}) , there is a unique value of the vector of model parameters \boldsymbol{g} that creates this distribution, which will be given in Eq. ( 46 ) (resp. ( 47 )). 2.1.2 Families of maximum entropy models for discrete data Equation ( 12 ) with the constraints ( 15 ) gives the most general parametric model able to reproduce all possible patterns of discrete data, expressed under the form of the multivariate moments ( 11 ). In the context of statistical modeling, besides being able to reproduce the data patterns, one also aims to distinguish patterns that are significant from those that are just noise (for example, in order to extract structural information about the modeled system, or for the model to better generalize). In other words, one aims to reduce the set of parameters of the model to only those that captures relevant patterns of the data. Identifying these relevant parameters can be addressed by comparing (sub-)models of the complete model, in which different sets of parameters have been exactly fixed to zero (before fitting), and selecting the best among them based on model selection criteria, as discussed in the introduction. In this context, the sub-models of ( 12 ), for which some of the complex parameters g_{\boldsymbol{\mu}} ’s have been set exactly to zero, form a complete family of maximum entropy models constrained on reproducing arbitrary subsets of moments of the spin variables from the data. Each of these sub-models is identified by the choice of a subset \mathcal{M}=\{\boldsymbol{\mu}_{1},\cdots,\boldsymbol{\mu}_{K}\}\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*} of operators for which the parameters g_{\boldsymbol{\mu}} are not set to zero and which identify the fitted moments. We use this notation to define the family of q -state spin models. Definition 5 . ( q -state spin models) Complete family of maximum entropy models constrained on reproducing arbitrary sets of spin moments. Consider a system of n q -state spin variables ( 10 ) \boldsymbol{s}=(s_{1},\,\cdots,\,s_{n}) . A q -state spin model is a parametric probability distribution of the form: p(\boldsymbol{s}\,|\,\boldsymbol{g},\mathcal{M})=\displaystyle\frac{1}{Z_{\mathcal{M}}(\boldsymbol{g})}\,\exp\left({\;\sum_{\boldsymbol{\mu}\in\mathcal{M}}g_{\boldsymbol{\mu}}\,\phi^{\boldsymbol{\mu}}(\boldsymbol{s})}\right) , (19) with \qquad\forall\boldsymbol{\mu}\in\mathcal{M}\,,\qquad-\boldsymbol{\mu}\in\mathcal{M} and g_{-\boldsymbol{\mu}}=g_{\boldsymbol{\mu}}^{*} , (20) where the set \mathcal{M}\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*} identifies the empirical moments \langle\phi^{\boldsymbol{\mu}}(\boldsymbol{s})\rangle that the model is constrained to reproduce when fitting the parameters g_{\boldsymbol{\mu}} ’s. The spin operators \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) are given by Eq. ( 13 ) and can be of arbitrary order. For the probabilities p(\boldsymbol{s}\,|\,\boldsymbol{g},\,\mathcal{M}) to be real, complex operators must be included by conjugate pairs in \mathcal{M} and the corresponding parameters must satisfy Eq. ( 20 ). The normalization factor Z_{\mathcal{M}}(\boldsymbol{g}) is the partition function of the model: \displaystyle Z_{\mathcal{M}}(\boldsymbol{g})=\displaystyle\sum_{\boldsymbol{s}}\;\exp\left(\,\sum_{\boldsymbol{\mu}\in\mathcal{M}}g_{\boldsymbol{\mu}}\,\phi^{\boldsymbol{\mu}}(\boldsymbol{s})\right)\,, (21) where \boldsymbol{g} is a vector containing all the parameters g_{\boldsymbol{\mu}} ’s and the first sum is over the q^{n} states of \boldsymbol{s} . The spin models in Eq. ( 19 ) can also be expressed in terms of the discrete variables \boldsymbol{\alpha} , by simply replacing the dependencies in \boldsymbol{s} by dependencies in \boldsymbol{\alpha} . For binary systems ( q=2 ), all the operators take real (binary) values \phi^{\boldsymbol{\mu}}(\boldsymbol{s})\in\{\pm 1\} , the parameters g_{\boldsymbol{\mu}} are real, and one recovers the family of high-order Ising models defined in Eq. ( 1 ) 34 ; 9 . Note that, if we relax the constraint that operators must be included in the model by conjugate pairs with conjugate parameters satisfying ( 20 ), then the energy function in the exponential can take complex values. This implies complex state probabilities and a complex partition function. Although this may not be physical for classical systems, it could still be worthy of study. For instance, extending the partition function to the complex plane has been commonly used to study phase transitions in finite size classical many-body systems 55 , including on complex networks 29 ; 30 . In the spin model ( 19 ), upon fitting the complex parameter g^{\boldsymbol{\mu}} , the model reproduces both the real and the imaginary parts of the corresponding moment \langle\phi^{\boldsymbol{\mu}}\rangle . More generally, one could choose to set to zero any of the (q^{n}-1) real parameters a_{\boldsymbol{\mu}} and b_{\boldsymbol{\mu}} in Eq. ( 16 ). This is different from the previous setting, because it allows the modeler to choose to reproduce only the real or the imaginary part of a given moment (as opposed to both of them simultaneously). This approach then corresponds to defining the following family of maximum entropy models, constrained to reproduce the real and/or the imaginary part of a selected set of moments of the spin variables: Definition 6 . Complete family of maximum entropy models for discrete data. Consider a system of n q -state discrete variables ( 9 ) \boldsymbol{\alpha}=(\alpha_{1},\,\cdots,\,\alpha_{n}) . The following exponential family of probability distributions defines a complete family of parametric models for discrete data: p(\boldsymbol{\alpha}\,|\,\boldsymbol{g},\mathcal{M})=\displaystyle\frac{1}{Z_{\mathcal{M}}(\boldsymbol{g})}\,\exp[\displaystyle\sum_{\boldsymbol{\mu}\in\mathcal{M}_{0}\cup\mathcal{M}_{Re}}a_{\boldsymbol{\mu}}\,\cos\left({\displaystyle\frac{2\pi}{q}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}}\right)+\displaystyle\sum_{\boldsymbol{\mu}\in\mathcal{M}_{Im}}b_{\boldsymbol{\mu}}\,\sin\left({\displaystyle\frac{2\pi}{q}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}}\right)\Bigg] (22) where a_{\boldsymbol{\mu}} and b_{\boldsymbol{\mu}} are real parameters. \mathcal{M}_{0} identifies an arbitrary set of real moments (for \boldsymbol{\mu}=-\boldsymbol{\mu} ), \langle\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})\rangle=\langle\varphi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})\rangle , that the model is constrained to reproduce, and \mathcal{M}_{Re} and \mathcal{M}_{Im} identify two arbitrary sets of complex moments (for \boldsymbol{\mu}\neq-\boldsymbol{\mu} ) for which the model is constrained to reproduce respectively the real part \langle\varphi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})\rangle and the imaginary part \langle\psi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})\rangle . These sets are chosen such that: \begin{cases}\;\mathcal{M}_{0}&\subseteq\{\,\boldsymbol{\mu}\in[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*}\mid\boldsymbol{\mu}=-\boldsymbol{\mu}\,\}\,,\\[1.0pt] \;\mathcal{M}_{Re}&\subseteq\{\,\boldsymbol{\mu}\in[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*}\mid\boldsymbol{\mu}<-\boldsymbol{\mu}\,\}\,,\\[1.0pt] \;\mathcal{M}_{Im}&\subseteq\{\,\boldsymbol{\mu}\in[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*}\mid\boldsymbol{\mu}<-\boldsymbol{\mu}\,\}\,,\end{cases} (23) where the ordering between vectors \boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n} is based on the ordering of the integers represented by \boldsymbol{\mu} in base q . The condition that \boldsymbol{\mu}<-\boldsymbol{\mu} is used so that \mathcal{M}_{Re} and \mathcal{M}_{Im} only contains one vector \boldsymbol{\mu} for each conjugate pair ( \forall\boldsymbol{\mu}\in\mathcal{M}_{Re}\,,\;-\boldsymbol{\mu}\notin\mathcal{M}_{Re} ). Special cases: – For odd values of q , \mathcal{M}_{0}=\emptyset . – The sets \mathcal{M}_{Re} and \mathcal{M}_{Im} can overlap. When these sets are equal, the model parametric distribution in Eq. ( 22 ) is identical to the one in Eq. ( 19 ) with \mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{Re}\cup(-\mathcal{M}_{Re}) , and the parameters a_{\boldsymbol{\mu}} and b_{\boldsymbol{\mu}} are related to the g_{\boldsymbol{\mu}} ’s by g_{\boldsymbol{\mu}}=(a_{\boldsymbol{\mu}}-ib_{\boldsymbol{\mu}})/2=g_{-\boldsymbol{\mu}}^{*} for all \boldsymbol{\mu}\in\mathcal{M}_{Re} and g_{\boldsymbol{\mu}}=a_{\boldsymbol{\mu}} for all \boldsymbol{\mu}\in\mathcal{M}_{0} . – For the binary case ( q=2 ), \mathcal{M}_{Re}=\mathcal{M}_{Im}=\emptyset and, for all \boldsymbol{\mu}\in\mathcal{M}_{0} , \varphi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=(-1)^{\boldsymbol{\alpha}\cdot\boldsymbol{\mu}} . We recover the family of binary spin models defined in Eq. ( 1 ). The families of models in Eq. ( 19 ) and Eq. ( 22 ) both generalize the family of binary spin models in Eq. ( 1 ) to values of q\geq 2 . 2.1.3 Interactions of arbitrary order between the variables In the maximum entropy models ( 19 ) and ( 22 ), the term in the exponential, which we denote -H(\boldsymbol{s}) , can be interpreted as (minus) the energy of the spin system, resulting from interactions between the spins. More precisely, the q -state spin models in Eq. ( 19 ) have the same form as the binary models in Eq. ( 1 ), but generalized to q\geq 2 . By analogy to the binary case, one can interpret the discrete vectors \boldsymbol{\mu} as encoding interactions (of arbitrary order) between the spins s_{j} for which \mu_{j}\neq 0 , with an interaction energy H^{\boldsymbol{\mu}}(\boldsymbol{s})=-g_{\boldsymbol{\mu}}\,\phi^{\boldsymbol{\mu}}(\boldsymbol{s})=-g_{\boldsymbol{\mu}}\,\prod_{j=1}^{n}s_{j}^{\mu_{j}} that depends only on the state of these variables. However, unlike the binary case, the contribution of each spin to the interaction energy is now weighted differently depending on the value of the \mu_{j} ’s, and therefore there can be different types of interactions involving the same set of spins. For example, for a binary system ( 1 ) with n=4 spins, the vector \boldsymbol{\mu}=(1,1,0,1) identifies the spin operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=s_{1}s_{2}s_{4} and is interpreted as encoding a 3-body interaction between the spins s_{1} , s_{2} , and s_{4} . In the ternary case q=3 , the vector \boldsymbol{\mu}=(2,1,0,1) identifies the spin operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=s_{1}^{2}s_{2}s_{4} and can similarly be interpreted as encoding a 3-body interaction between the same spins, but the spin s_{1} is now weighted twice in the interaction. The vector \boldsymbol{\mu}=(1,1,0,1) also encodes a 3-body interaction between the same spins, but it has a different interaction energy. Indeed, different values of \mu_{j} weight the colors \alpha_{j} differently in the operator \phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=\exp\big((2i\pi/q)\sum_{j=1}^n \mu_j\,\alpha_j\big) , thus resulting in different contributions to the energy landscape. In Sec. 2.4 , we discuss the interpretation of different types of interaction involving the same spins. Similarly, in Eq. ( 22 ), each vector \boldsymbol{\mu} can be interpreted as encoding an interaction, whose energy H^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=-a_{\boldsymbol{\mu}}\varphi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})-b_{\boldsymbol{\mu}}\psi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=-a_{\boldsymbol{\mu}}\cos((2\pi/q)\,\vecmu\cdot\state)-b_{\boldsymbol{\mu}}\sin((2\pi/q)\,\vecmu\cdot\state) only depends on the values taken by the spins s_{j} for which \mu_{j}\neq 0 . More generally: Definition 7 . Arbitrary-order interactions. For a system of n random variables \boldsymbol{\alpha}=(\alpha_{1},\,\cdots,\,\alpha_{n}) , one can identify an interaction of arbitrary order by: – an n -dimensional vector \boldsymbol{\mu}\in\mathbb{N}^{n} , whose non-zero entries identify which variables interact, – and an interaction energy H^{\boldsymbol{\mu}}(\boldsymbol{\alpha}) that defines how the variables interact and whose functional form depends only on the variables \alpha_{j} for which \mu_{j}\neq 0 . For example, for the models discussed in this paper, H^{\boldsymbol{\mu}}(\boldsymbol{\alpha}) depends on the scalar product \boldsymbol{\mu}\cdot\boldsymbol{\alpha}=\sum_{j}\mu_{j}\,\alpha_{j} . In the cases considered here, the interaction energies, H^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=g_{\boldsymbol{\mu}}\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha}) or H^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=a_{\boldsymbol{\mu}}\varphi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})+b_{\boldsymbol{\mu}}\psi^{\boldsymbol{\mu}}(\boldsymbol{\alpha}) , are non-linear functions of a linear combination \boldsymbol{\mu}\cdot\boldsymbol{\alpha}=\sum_{j}\mu_{j}\,\alpha_{j} of the colors of the spins involved in the interaction encoded by \boldsymbol{\mu} . Definition 8 . Order of an interaction. The order of an interaction corresponds to the number of variables involved in the interaction. For an interaction identified by a vector \boldsymbol{\mu} , it is given by the numbers of non-zero entries in \boldsymbol{\mu} , which is |\boldsymbol{\mu}|=\sum_{j=1}^{n}(1-\delta_{0,\mu_{j}}) . Note that this is not the same as the order of the operator identified by \boldsymbol{\mu} (or of the corresponding moment), which is \sum_{i=1}^{n}\mu_{i} . 2.2 Comparison with other models for discrete systems 2.2.1 Examples of pairwise discrete models Example 1 . The planar Potts model ( 41 ) (also known as vector Potts model or clock model). In this model, spins take q discrete values uniformly distributed around the unit circle, as in Eq. ( 10 ), and are placed on a lattice or, more generally, on the nodes of a network. Spins connected by a link in the network interact and the Hamiltonian of the system is given by: \displaystyle H(\boldsymbol{\alpha})=-\displaystyle\sum_{\langle i,j\rangle}J_{ij}\,\cos\left(\displaystyle\frac{2\pi}{q}(\alpha_{i}-\alpha_{j})\right)\,, (24) where \langle i,j\rangle denotes the pairs of nodes i,j that are connected by a link in the network. In the original model, there is only one parameter, J_{ij}=J for all pairs \langle i,j\rangle . Here, we adopted a more general notation, where the coupling parameters J_{ij} can take different values. The models we introduced in ( 19 ) and ( 22 ) can be seen as high-order generalizations of the planar Potts model. Indeed, it is straightforward to check that the Hamiltonian in Eq. ( 24 ) corresponds to a model of the form of Eq. ( 22 ), in which b_{\boldsymbol{\mu}}=0 for all \boldsymbol{\mu} and all the interactions are pairwise of the type: for each pair of nodes (i,j) connected by a link, there is one interaction vector \boldsymbol{\mu} such that 7 7 7 Which of the two nodes is ‘ i ‘ or ‘ j ‘ doesn’t matter. One could choose to take the conjugate operators instead in \mathcal{M}_{0}\cup\mathcal{M}_{Re} , i.e. the operator \boldsymbol{\mu} with \mu_{i}=(q-1) and \mu_{j}=1 . This would give the exact same model. \displaystyle\mu_{i}=1\,,\qquad\qquad\mu_{j}=(q-1)\,,\qquad{\rm and}\qquad\mu_{k}=0\;\qquad\forall k\neq i,j\,. (25) The corresponding operator \varphi^{\boldsymbol{\mu}}(\boldsymbol{\alpha}) in ( 22 ) is then given by: \displaystyle\cos\left(\frac{2\pi}{q}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}\right)=\cos\left(\frac{2\pi}{q}\left(\alpha_{i}+(q-1)\alpha_{j}\right)\right)=\cos\left(\frac{2\pi}{q}(\alpha_{i}-\alpha_{j})\right)\,. (26) Note that the contribution of each pairwise interaction in Eq. ( 24 ) can also be written as a scalar product between the vectors representing the two spins in the complex plane: \displaystyle H(\boldsymbol{s})=-\displaystyle\sum_{\langle i,j\rangle}J_{ij}\;\vec{s}_{i}\cdot\vec{s}_{j}\,, (27) where \vec{s}_{j}=(\cos(\frac{2\pi\alpha_j}{q}),\sin(\frac{2\pi\alpha_j}{q})) . Similarly, a maximum entropy model constrained to reproduce the imaginary parts of the same moments would take the form: \displaystyle H(\boldsymbol{\alpha})=-\sum_{\langle i,j\rangle}J_{ij}\,\sin\left(\displaystyle\frac{2\pi}{q}(\alpha_{i}-\alpha_{j})\right)=-\Bigg(\displaystyle\sum_{\langle i,j\rangle}J_{ij}\;\vec{s}_{i}\times\vec{s}_{j}\Bigg)\cdot\vec{e}_{z}\,. (28) where \times denotes the vector product between the spin vectors \vec{s}_{j}=(\cos(\frac{2\pi\alpha_j}{q}),\sin(\frac{2\pi\alpha_j}{q}),0) representing the planar spins in a 3-dimensional space, and \vec{e}_{z}=(0,0,1) . This produces a model with antisymmetric interactions in the values taken by the pair \alpha_{i} and \alpha_{j} . Although the planar Potts model wasn’t introduced in the context of statistical inference, one may wonder if it could be used to model the pairwise structure of discrete data. In Eq. ( 24 ), each pairwise interaction is parameterized by 1 parameter. If we were to also fit the corresponding imaginary part, we would have 2 parameters. However, to fully parameterize all the pairwise moments based on a given pair of spins, one needs a total of (q-1)^{2} real parameters 8 8 8 The number of pairwise operators on a given pair of spins is equal to the number of possible values of the pair (\mu_{i},\mu_{j})\in\{1,\cdots,(q-1)\}^{2} ( \mu_{i} and \mu_{j} must be both non-zero for \boldsymbol{\mu} to encode an interaction between \alpha_{i} and \alpha_{j} ). Besides, there are two independent real parameters for each pair of conjugate operators, and thus one can count the number of independent parameters as being equal to the number of operators (see Sec. 2.1.1 ). . For example, for q=3 and n=2 spins, one needs 4 real parameters: 2 to parameterize the conjugate operators (1,2) and (2,1) , and 2 for the conjugate operators (1,1) and (2,2) (see Sec. 2.4 for a discussion on the meaning of these different interactions). These latter are not accounted for in Eq. ( 24 ), but are needed to fully parameterize statistical patterns of pairs of spins. In the context of statistical inference, a common parametric model that can account for all first and second order patterns of discrete data is the following. Example 2 . Generalized pairwise Potts model for statistical inference. A generalization of the Potts model commonly used in statistical inference 39 takes the form: \displaystyle H(\boldsymbol{\alpha})=\sum_{}J_{ij}(\alpha_{i},\alpha_{j})+\sum_{i}h_{i}(\alpha_{i})\,, (29) where the coupling parameters J_{ij} and field parameters h_{i} can take different values for each state of the nodes \alpha_{i} and \alpha_{j} , i.e., J_{ij}(\alpha_{i},\alpha_{j}) is the energy of the interaction between nodes i and j when they take the value (\alpha_{i},\alpha_{j}) . Note that J_{ij}(\alpha,\alpha^{\prime}) is not necessarily equal to J_{ij}(\alpha^{\prime},\alpha) . The form of this model is different from the one in Eq. ( 19 ) and ( 22 ) reduced to all first and second order interactions. Although each of these models is able to fit all the pairwise patterns of discrete data, the model ( 29 ) has more parameters than the number of pairwise constraints in the system. In total, there are q real parameters for h_{i}(\alpha_{i}) (one for each value of \alpha_{i} ) and q^{2} parameters for each pairwise interactions (one for each value of (\alpha_{i},\alpha_{j}) ), while there are only (q-1) moments based on a given spin and (q-1)^{2} moments on a given pair of spins. This overparameterization results in the parameters of Eq. ( 29 ) being defined up to a gauge 17 ; 6 ; 46 , which is not the case for Eq. ( 19 ) and ( 22 ). The parameters of ( 29 ) are related to the parameters of ( 19 ) and ( 22 ) by: \displaystyle\begin{cases}&h_{j}(\alpha_{j})=\displaystyle\sum_{\mu_{j}=1}^{q-1}g_{\mu_{j}}\exp\left(\frac{2i\pi}{q}\mu_{j}\alpha_{j}\right)\,,\qquad\forall\alpha_{j}\\ &J_{ij}(\alpha_{i},\alpha_{j})=\displaystyle\sum_{\mu_{i}=1}^{q-1}\sum_{\mu_{j}=1}^{q-1}g_{\mu_{i}\mu_{j}}\exp\left(\frac{2i\pi}{q}(\mu_{i}\alpha_{i}+\mu_{j}\alpha_{j})\right)\,,\qquad\forall(\alpha_{i},\alpha_{j})\end{cases} (30) where g_{\mu_{j}} (resp. g_{\mu_{i}\mu_{j}} ) denotes the parameter g_{\boldsymbol{\mu}} for which the j -th (resp. i -th and j -th) element of \boldsymbol{\mu} is \mu_{j} (resp. \mu_{i} and \mu_{j} ) and all the other elements are 0 . We recall that g_{-\boldsymbol{\mu}}=g_{\boldsymbol{\mu}}^{*}=(a_{\boldsymbol{\mu}}+ib_{\boldsymbol{\mu}})/2 . On the left-hand-side, there are q+q^{2} parameters, while on the right-hand-side, there are (q-1)+(q-1)^{2} independent real parameters a_{\boldsymbol{\mu}} and b_{\boldsymbol{\mu}} . For example, for a system with q=3 and n=2 variables \boldsymbol{\alpha}=(\alpha_{1},\alpha_{2}) , the one-body terms are parametrized as: \displaystyle h_{j}(\alpha_{j}) \displaystyle=g_{(10)}z_{3}^{\alpha_{j}}+g_{(20)}z_{3}^{2\alpha_{j}}\,,\qquad{\rm with}\;g_{20}=g_{10}^{*} \displaystyle=a_{(10)}\cos\left(\frac{2\pi}{3}\alpha_{j}\right)+b_{(10)}\sin\left(\frac{2\pi}{3}\alpha_{j}\right)\,, where there are three parameters h_{j} on the left-hand side and only two real parameters on the right-hand side. The pairwise interaction is parametrized as: \displaystyle J_{12}(\alpha_{1},\alpha_{2}) \displaystyle=g_{(11)}z_{3}^{\alpha_{1}+\alpha_{2}}+g_{(22)}z_{3}^{2\alpha_{1}+2\alpha_{2}}+g_{(12)}z_{3}^{\alpha_{1}+2\alpha_{2}}+g_{(21)}z_{3}^{2\alpha_{1}+\alpha_{2}}\,,\;{\rm with}\;g_{22}=g_{11}^{*}\,,\;g_{21}=g_{12}^{*} \displaystyle=a_{(11)}\cos\Big(\frac{2\pi}{3}(\alpha_1+\alpha_2)\Big)+b_{(11)}\sin\Big(\frac{2\pi}{3}(\alpha_1+\alpha_2)\Big) \displaystyle\qquad+a_{(12)}\cos\Big(\frac{2\pi}{3}(\alpha_1-\alpha_2)\Big)+b_{(12)}\sin\Big(\frac{2\pi}{3}(\alpha_1-\alpha_2)\Big)\,, where there are nine parameters J_{ij} on the left-hand side and only four real parameters on the right-hand side Example 3 . Continuous limit and XY model. In the limit q\to\infty , the planar Potts model ( 24 ) becomes the XY model (after adding one-body contributions): \displaystyle H(\boldsymbol{s})=-\displaystyle\sum_{\langle i,j\rangle}J_{ij}\,\cos\left(\theta_{i}-\theta_{j}\right)-\displaystyle\sum_{j}h_{j}\,\cos\left(\theta_{j}\right)\,, (31) where the variable \theta_{j}\in[0,\,2\pi] corresponds to the angle that the planar spin \vec{s}_{j} forms with the x -axis. Before taking the limit q\to\infty , \theta_{j} is related to the variable \alpha_{j}\in(\mathbb{Z}/q\mathbb{Z})^{n} by \theta_{j}=\frac{2\pi}{q}\alpha_{j} . Similarly, defining the angle \theta_{j}=\frac{2\pi}{q}\alpha_{j} for each value of \alpha_{j}\in(\mathbb{Z}/q\mathbb{Z})^{n} and taking the limit q\to\infty , the model in Eq. ( 22 ) can be seen as a generalization of the XY model to higher-order interactions, where now the vectors \boldsymbol{\mu}\in\mathbb{N}^{n} . Note that after taking q\to\infty , \theta_{j} takes real values in [0,2\pi] , but \alpha_{j} remains an integer, \alpha_{j}\in\mathbb{N} . 2.2.2 Examples of high-order discrete models Example 4 . High-order generalization of the standard Potts model. Ref. 20 introduced a high-order generalization of the standard Potts 54 model of the form: \displaystyle H(\boldsymbol{\alpha}\,|\,E)=-\displaystyle\sum_{e\in E}J_{e}\,\delta_{e}(\boldsymbol{\alpha})\,,\qquad{\rm where}\qquad\delta_{e}(\boldsymbol{\alpha})=\begin{cases}\;1&{\rm if}\;\;\alpha_{i}=\alpha_{j}\;\;{\rm for\;all}\;\;i,j\in e\\ \;0&{\rm otherwise}\end{cases} (32) where is E set of hyperedges e between the variables. \delta_{e}(\boldsymbol{\alpha})=1 only if all the spins connected by e have the same value. When all hyperedges are pairwise, one recovers the standard Potts model. Although this model wasn’t introduced in the context of statistical inference, one may wonder if it could be used for this purpose. Similarly to our own case, each operator \delta_{e}(\boldsymbol{\alpha}) defines a (high-order) interaction between the spins connected by the hyperedge e . However, the interaction energy -J_{e}\delta_{e}(\boldsymbol{\alpha}) can only take two values (instead of q in our case) and is unable to distinguish states for which the variables \alpha_{i} connected by e take non-equal values. In particular, it doesn’t allow to weigh differently the contributions of different spins to the same interaction. This is an issue for statistical inference, because one aims to model how similar or different the values taken by the random variables are. Besides, each hyperedge e is only associated to one interaction (compared to (q-1)^{|e|} in our case). This means that there are at most (2^{n}-1) different \delta_{e} -functions, which is not sufficient to form a basis of \mathbb{R}[(\mathbb{Z}/q\mathbb{Z})^{n}] for q>2 , and therefore a full model of the form of Eq. ( 32 ) wouldn’t be able to capture all patterns of discrete data for q>2 . For q=2 , this model could a priori model all possible patterns of binary data, if the set of \delta_{e} -functions forms a basis of \mathbb{R}[(\mathbb{Z}/2\mathbb{Z})^{n}] (this remains to be checked) and after adding terms of order one (self-interactions). If this were the case, this basis would differ from the Ising spin basis studied here, decomposing multi-variate information in a different manner. Note that models of the form ( 32 ) with only pairwise interactions e=(ij) , can be mapped to pairwise Ising models using \delta_{ij}(\boldsymbol{\alpha})=(1+\phi^{(ij)}(\boldsymbol{\alpha}))/2 , where (ij) denotes the vector \boldsymbol{\mu} in which \mu_{i}=\mu_{j}=1 and all the other elements are zero. Example 5 . Other high-order models for discrete systems. Ref. 51 recently introduced another model for the statistical inference of three-state systems inspired by the Blume-Capel model 10 ; 12 from condensed matter. This model corresponds to a maximum entropy model constrained on reproducing multivariate moments of the discrete variables \boldsymbol{\alpha} , instead of moments of the spin variables \boldsymbol{s} . So far, this model only includes interactions up to pairwise, but can easily be generalized by constraining the model on higher-order moments as well. Another approach in the context of statistical modeling is the one by Ref. 23 , which defines models constrained to reproduce high-order cumulants from multivariate data. 2.3 Properties of q -state spin models and discrete Fourier analysis In this section, we show that the set of q^{n} complex spin operators ( 13 ) forms an orthonormal basis of the vector space of complex functions over (\mathbb{Z}/q\mathbb{Z})^{n} , and thus that the model ( 12 ) corresponds to a particular choice of basis decomposition of the multivariate log-probability, more specifically to a (spatial) Fourier decomposition. Similarly, Eq. ( 16 ) corresponds to a decomposition of the log-probability over the (spatial) trigonometric Fourier basis. The properties discussed below extend results known in the binary case 9 to the more general discrete case q\geq 2 . They are direct consequences of the operators being Fourier basis functions. The advantage of mapping Eq. ( 12 ) and ( 16 ) to Fourier series is that it enables the use of Fourier analysis tools for statistical inference (e.g., efficient algorithms to compute the Fourier coefficients can be used to compute the model parameters 27 ; 11 ; 36 ; 40 ). 2.3.1 Spin models as Fourier decompositions of the log-probability Property 1 . Group \Omega of complex spin operators. The set \Omega of all the q^{n} spin monomials ( 13 ) forms a finite multiplicative group with identity element \phi^{\boldsymbol{0}}(\boldsymbol{s})=1 . It is the cyclic group of order q generated by the spin variables s_{1},s_{2},\cdots,s_{n} : \displaystyle\Omega\doteq\{\phi^{\boldsymbol{\mu}}(\boldsymbol{s})\mid\boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n}\}\,=\;\langle s_{1},s_{2},\cdots,s_{n}\rangle_{gen}\,. (33) where, for all j , the variable s_{j} takes values in the q -th roots of unity ( 10 ). Proof. From Definition 4 , it is straightforward that, for all (\boldsymbol{\mu},\boldsymbol{\nu})\in[(\mathbb{Z}/q\mathbb{Z})^{n}]^{2} , \displaystyle\phi^{\boldsymbol{\mu}}(\boldsymbol{s})\,\phi^{\boldsymbol{\nu}}(\boldsymbol{s})=\phi^{\boldsymbol{\mu}+\boldsymbol{\nu}}(\boldsymbol{s})\in\Omega\,, (34) is also a monomial that belongs to \Omega , where the sum \boldsymbol{\mu}+\boldsymbol{\nu} is performed on (\mathbb{Z}/q\mathbb{Z})^{n} (i.e. with modulo q ). The inverse of an operator is [\phi^{\boldsymbol{\mu}}(\boldsymbol{s})]^{-1}=\phi^{-\boldsymbol{\mu}}(\boldsymbol{s})=[\phi^{\boldsymbol{\mu}}(\boldsymbol{s})]^{*} . In the binary case, each operator is its own inverse. Each element of \Omega is at most of order q , as: \displaystyle[\phi^{\boldsymbol{\mu}}(\boldsymbol{s})]^{q}=\exp\left({\displaystyle 2i\pi\,\boldsymbol{\alpha}\cdot\boldsymbol{\mu}}\right)=1\,,\qquad\qquad\forall\;\boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n}\,. (35) ∎ Property 2 . Sum of spin operator values. The monomials \phi^{\boldsymbol{\mu}}(\boldsymbol{s})\in\Omega verify that: \displaystyle\sum_{\boldsymbol{s}}\phi^{\boldsymbol{\mu}}(\boldsymbol{s})=\sum_{\boldsymbol{\alpha}\in(\mathbb{Z}/q\mathbb{Z})^{n}}\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=q^{n}\,\delta_{\boldsymbol{\mu},\boldsymbol{0}}\,,\qquad\qquad\forall\;\boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n}\,, (36) where the two sums are respectively over all possible q^{n} states of \boldsymbol{s} and \boldsymbol{\alpha} , and where the delta function \delta_{\boldsymbol{\mu},\boldsymbol{0}} is equal to 1 if \boldsymbol{\mu}=\boldsymbol{0} and to 0 otherwise. Replacing the expression of \phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha}) in Eq. ( 36 ), and identifying the real and the imaginary parts on the two sides of the equality, one obtains a similar property for \varphi^{\boldsymbol{\mu}} and \psi^{\boldsymbol{\mu}} : \displaystyle\forall\boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n}\,,\;\;\sum_{\boldsymbol{\alpha}\in(\mathbb{Z}/q\mathbb{Z})^{n}}\cos\left(\frac{2\pi}{q}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}\right)=q^{n}\,\delta_{\boldsymbol{\mu},\boldsymbol{0}}\qquad{\rm and}\;\;\sum_{\boldsymbol{\alpha}\in(\mathbb{Z}/q\mathbb{Z})^{n}}\sin\left(\frac{2\pi}{q}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}\right)=0\,. (37) Equation ( 36 ) is a direct consequence of the fact that the variables s_{j} are roots of unity, which satisfy 9 9 9 For all \mu_{j}\in(\mathbb{Z}/q\mathbb{Z}) , \sum_{s_{j}}s_{j}^{\mu_{j}}=\sum_{\alpha_{j}=0}^{q-1}e^{\frac{2i\pi}{q}\alpha_{j}\,\mu_{j}}=\frac{1-\Big(e^{\frac{2i\pi}{q}\mu_{j}}\Big)^{q}}{1-e^{\frac{2i\pi}{q}\mu_{j}}}=0\,. \sum_{s_{j}}s_{j}^{\mu}=0 for all strictly positive integer \mu . It reflects that, similarly to s_{j} , the values taken by \phi^{\boldsymbol{\mu}}(\boldsymbol{s}) as one varies \boldsymbol{s} are evenly distributed over the q -th roots of unity 10 10 10 Or evenly distributed over the q^{\prime} -th roots of unity, if q is non-prime and q^{\prime}2 , both in Eq. ( 57 ) and Eq. ( 67 ). However, this term doesn’t necessarily correspond to the partition function one would get for an independent model. In the following, we give the definition of independent models for complex- and real-valued q -state spin models, which we then use to write the partition function in the form of a cluster expansion. 3.3.1 General expression The definition of independent models 9 ; 15 can be easily extended to q\geq 2 . To do so, we first introduce the notion of independence between spin operators, from which follows a natural definition of independent models. Definition 11 . Independent set of operators. Consider a system of n q -state spin variables. A set of operators \{\phi^{\boldsymbol{\mu}_{1}},\,\dots,\phi^{\boldsymbol{\mu}_{K}}\} is said independent if and only if the set of vectors \mathcal{S}=\{\boldsymbol{\mu}_{1},\,\dots,\boldsymbol{\mu}_{K}\} is linearly independent in (\mathbb{Z}/q\mathbb{Z})^{n} : \displaystyle\forall(r_{k})\in(\mathbb{Z}/q\mathbb{Z})^{K},\;\;\;\;\sum_{k=1}^{K}r_{k}\,\boldsymbol{\mu}_{k}=\boldsymbol{0}\;({\rm mod}\;q)\qquad\Rightarrow\qquad r_{k}=0\;\;\;\;\forall\,k\,. (71) This is equivalent to the set of loops of \mathcal{S} containing only the null vector: \mathcal{L}_{q}(\mathcal{S})=\{\boldsymbol{0}\} . Definition 12 . Independent model. A q -state spin model is said independent if the set \mathcal{M} of operators of the model is an independent set, or equivalently, if the set of loops of the model only contains the null vector (empty loop) \mathcal{L}_{q}(\mathcal{M})=\{\boldsymbol{0}\} . Property 11 . Partition function of an independent model: Consider an independent model \mathcal{M}_{ind} for any q\geq 2 . Taking the term corresponding to the empty loop in Eq. ( 57 ), the partition function of \mathcal{M}_{ind} takes the form: \displaystyle{\rm for}\;q\geq 2\,,\qquad Z_{\mathcal{M}_{ind}}(\boldsymbol{g})=q^{n}\,\prod_{\boldsymbol{\mu}\in\mathcal{M}_{ind}}c_{0}(g_{\boldsymbol{\mu}})\,,\qquad{where}\;\;c_{0}(x)=\sum_{k\geq 0}\frac{x^{kq}}{(kq)!}\,. (72) This equation generalizes Eq. ( 69 ) to larger values of q , as c_{0}(x)=\cosh(x) for q=2 . The partition function ( 57 ) can then be rewritten under the following form. Property 12 . Cluster expansion of the partition of q -state spin models: Consider a q -state spin model \mathcal{M} with K operators arbitrarily indexed as \mathcal{M}=\{\boldsymbol{\mu}_{1},\cdots,\,\boldsymbol{\mu}_{K}\} . For all q\geq 2 , the partition function of \mathcal{M} can be written under the cluster expansion form: \displaystyle Z_{\mathcal{M}}(\boldsymbol{g})=Z^{ind}_{\mathcal{M}}(\boldsymbol{g})\,\left[\,1+\sum_{\boldsymbol{\ell}\in\mathcal{L}_{q}(\mathcal{M})\backslash\boldsymbol{0}}\;\prod_{k=1}^{K}\frac{c_{\ell_{k}}}{c_{0}}(g_{\boldsymbol{\mu}_{k}})\,\right]\,, (73) where the coefficients c_{\ell}(x) are given in Eq. ( 57 ), and where Z^{ind}_{\mathcal{M}}(\boldsymbol{g}) is the partition function of \mathcal{M} computed as if \mathcal{M} was an independent model, which is given by Eq. ( 72 ). For q=2 , this equation reduces to the known Eq. ( 70 ), using that c_{0}(x)=\cosh(x) and c_{1}(x)=\sinh(x) . 3.3.2 Real-valued spin models For real-valued spin models, we recall that operators must be included by conjugate pairs in the model for the Hamiltonian to be real. It is clear that two conjugate operators \boldsymbol{\mu}_{1} and \boldsymbol{\mu}_{2} are not independent from each other, as they satisfy \boldsymbol{\mu}_{1}=-\boldsymbol{\mu}_{2} . However, we previously obtained a more explicit form of the loop expansion of the partition function ( 67 ) by computing analytically the contributions of complex conjugate operators (thus removing them from the loop structure). To obtain a similar form for the cluster expansion, we extend the definition of independent models to real-valued q -state spin models, by requiring independence only for one element for each conjugate pair. Definition 13 . Real-valued independent model. Using the decomposition of Definition 10 , a real-valued spin model \mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} is said independent if \mathcal{M}_{0}\cup\mathcal{M}_{1} is an independent set of operators. Although the decomposition of \mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*}\, is not unique, this definition doesn’t depend on the precise assignment of the conjugate operators to \mathcal{M}_{1} and \mathcal{M}_{1}^{*} , because the elements of \mathcal{M}_{1} and \mathcal{M}_{1}^{*} are related by just a sign change. The absence of dependencies among the operators in \mathcal{M}_{0}\cup\mathcal{M}_{1} of an independent model means that the model doesn’t contain any (non-empty) loop, except for the trivial loops due to c.c. operators in \mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} . Reciprocally, a real-valued model that doesn’t contain any loop, except due to c.c. operators, verifies the definition of independence. Corollary 1 . A real-valued independent model is a model whose set of loops in Eq. ( 58 ) only contains: 1) the empty loop, and 2) trivial loops due to c.c. operators. Equivalently, it is a model whose reduced set of loops in Eq. ( 68 ) solely contains the empty loop, \mathcal{L}^{cc}_{q}=\{(\boldsymbol{0},\,\boldsymbol{0})\} . The partition function expansion in Eq. ( 67 ) thus already separates the contributions obtained as if the real-valued model were independent, for which (\boldsymbol{\ell}_{0},\boldsymbol{\ell}_{1})=(\boldsymbol{0},\,\boldsymbol{0}) , from the contributions resulting from non-trivial loop constraints between the operators, for which (\boldsymbol{\ell}_{0},\boldsymbol{\ell}_{1})\neq(\boldsymbol{0},\,\boldsymbol{0}) . Note that we kept \mathcal{M}_{0} in definition 13 , because it allows the definition to be also valid for spin models with q=2 (which are already real-valued without having to introduce the structure of c.c. operators). Indeed in the binary case, \mathcal{M}_{1}=\emptyset and the definition and corollary above are consistent with the previous definition of independent models 9 ; 15 . For q>2 , any operator \boldsymbol{\mu}\in\mathcal{M}_{0} verifies that 2\boldsymbol{\mu}=\boldsymbol{0} (by definition of \mathcal{M}_{0} ) and therefore doesn’t satisfy the condition of independence in Eq. ( 71 ). This means that, for q>2 , independent models have \mathcal{M}_{0}=\emptyset . The term corresponding to the empty loop ( \boldsymbol{\ell}_{1}=\boldsymbol{0} ) in the partition function ( 67 ) then gives the partition function of a real-valued independent model for q>2 . Property 13 . Partition function of a real-valued independent model for q>2 : Consider a real-valued independent model \mathcal{M}_{Rind} for q>2 . Using the decomposition of Definition 10 , \mathcal{M}_{Rind}=\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} and the partition function of \mathcal{M}_{Rind} takes the form (term \boldsymbol{\ell}_{1}=\boldsymbol{0} in Eq. ( 67 )): \displaystyle{\rm for}\;q>2\,,\qquad Z_{\mathcal{M}_{Rind}}(\boldsymbol{g}) \displaystyle=q^{n}\,\prod_{\boldsymbol{\mu}_{1}\in\mathcal{M}_{1}}\,\left[\,\sum_{m=0}^{q-1}\left\lVert c_{m}(g_{\boldsymbol{\mu}_{1}})\right\rVert^{2}\,\right]\,,\;\;\;\;\; (74) where the c_{m}(x) are complex coefficients given in Eq. ( 57 ) and \lVert c_{m}(x)\rVert=\sqrt{c_{m}(x)\,c_{m}(x^{*})} denotes the norm of c_{m}(x) (because c_{m}(x^{*})=[c_{m}(x)]^{*} ). To obtain Eq. ( 74 ) from Eq. ( 67 ), we used that B_{0}(x)=\sum_{m=0}^{q-1}c_{m}(x)c_{m}(x^{*}) from Eq. ( 64 ). For example, for q=3 , \displaystyle Z_{\mathcal{M}_{Rind}}(\boldsymbol{g})=3^{n}\,\prod_{\boldsymbol{\mu}_{1}\in\mathcal{M}_{1}}\Big[c_{0}(g_{\boldsymbol{\mu}_{1}})\,c_{0}(g_{\boldsymbol{\mu}_{1}}^{*})+c_{1}(g_{\boldsymbol{\mu}_{1}})\,c_{1}(g_{\boldsymbol{\mu}_{1}}^{*})+c_{2}(g_{\boldsymbol{\mu}_{1}})\,c_{2}(g_{\boldsymbol{\mu}_{1}}^{*})\Big]\,, which gives back Eq. ( 59 ), previously obtained for a model with a single conjugate pair. For q>2 , for models for which \mathcal{M}_{0}=\emptyset (this is always the case if q is prime), the partition function ( 67 ) can then be written under the following cluster expansion form. Property 14 . Cluster expansion of the partition of a real-valued model \mathcal{M}=\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} (for q>2 ): Consider a real-valued spin model \mathcal{M}=\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} , for which \mathcal{M}_{0}=\emptyset in the decomposition of Definition 10 . We denote by K_{1}=|\mathcal{M}_{1}| the number of operators in \mathcal{M}_{1} and arbitrarily index the operators, \mathcal{M}_{1}=\{\boldsymbol{\mu}_{1,1},\cdots,\,\boldsymbol{\mu}_{1,K_{1}}\} . The partition function of \mathcal{M} can then be written under the cluster expansion form: \displaystyle Z_{\mathcal{M}}(\boldsymbol{g})=Z^{Rind}_{\mathcal{M}}(\boldsymbol{g})\,\left[\,1+\sum_{\boldsymbol{\ell}_{1}\in\mathcal{L}^{cc}_{q}(\mathcal{M}_{1})\backslash\boldsymbol{0}}\;\prod_{j=1}^{K_{1}}\frac{B_{\ell_{1,j}}}{B_{0}}(g_{\boldsymbol{\mu}_{1,j}})\,\right]\,, (75) where the coefficients B_{r}(x) are given by Eq. ( 64 ), and where Z^{Rind}_{\mathcal{M}}(\boldsymbol{g}) is the partition function of \mathcal{M} computed as if it were a real-valued independent model, which is given by Eq. ( 74 ). For clarity, we simplified the notation (\boldsymbol{\ell}_{0},\boldsymbol{\ell}_{1})\in\mathcal{L}^{cc}_{q}(\mathcal{M}_{0},\mathcal{M}_{1})\backslash(\boldsymbol{0},\boldsymbol{0}) into \boldsymbol{\ell}_{1}\in\mathcal{L}^{cc}_{q}(\mathcal{M}_{1})\backslash\boldsymbol{0} , because \mathcal{M}_{0}=\emptyset . This cluster expansion is always valid when q>2 is prime . More generally, for real-valued models with \mathcal{M}_{0}\neq\emptyset , we can factorize the term corresponding to the empty loop (\boldsymbol{\ell}_{0},\boldsymbol{\ell}_{1})=(\boldsymbol{0},\boldsymbol{0}) in Eq. ( 67 ), which gives the following general expression of the cluster expansion: \displaystyle Z_{\mathcal{M}}(\boldsymbol{g})=\frac{Z^{ind}_{\mathcal{M}_{0}}(\boldsymbol{g}_{0})}{2^{n}}\,Z^{Rind}_{\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*}}(\boldsymbol{g}_{1})\,\left[\,1+\sum_{(\boldsymbol{\ell}_{0},\boldsymbol{\ell}_{1})\in\mathcal{L}^{cc}_{q}(\mathcal{M}_{0},\mathcal{M}_{1})\backslash(\boldsymbol{0},\boldsymbol{0})}\;\prod_{i=1}^{K_{0}}\frac{A_{\ell_{0,i}}}{A_{0}}(g_{\boldsymbol{\mu}_{0,i}})\prod_{j=1}^{K_{1}}\frac{B_{\ell_{1,j}}}{B_{0}}(g_{\boldsymbol{\mu}_{1,j}})\,\right]\,, (76) where we can now recognize the factorized term as the partition function of \mathcal{M} computed as if: 1) the elements in \mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} were to form a real-valued independent model Z^{Rind}_{\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*}}(\boldsymbol{g}_{1})=q^{n}\prod_{j=1}^{K_{1}}B_{0}(g_{\boldsymbol{\mu}_{1,j}}) as in Eq. ( 74 ), and 2) the elements in \mathcal{M}_{0} were to form an binary independent model Z^{ind}_{\mathcal{M}_{0}}(\boldsymbol{g}_{0})=2^{n}\prod_{i=1}^{K_{0}}A_{0}(g_{\boldsymbol{\mu}_{0,i}}) as in Eq. ( 69 ) (with A_{0}(x)=\cosh(x) ). 3.3.3 Additional considerations when q is not prime When q is not prime, some operators \boldsymbol{\mu} other than those in \mathcal{M}_{0} can create “ self-loops ” of the form \eta\,\boldsymbol{\mu}=0 , where \eta is an integer strictly smaller than q . Just like for the operators in \mathcal{M}_{0} , these operators cannot contribute to an independent model, because they don’t satisfy Eq. ( 71 ). We call them self-dependent operators. Because of these operators, the notion of independent models may seem ambiguous. For example, consider a model for q=6 with a single pair of c.c. operators \mathcal{M}=\{\boldsymbol{\mu},-\boldsymbol{\mu}\} that verifies the self-dependence relation 3\boldsymbol{\mu}=0 (e.g., the one-body operator \boldsymbol{\mu}=(2) for a system with a single spin variable). This model has two loops in Eq. ( 68 ), the empty loop \boldsymbol{\ell}_{1}=(0) and the self-loop \boldsymbol{\ell}_{1}=(3) , which yields the partition function ( 67 ): \displaystyle Z_{\mathcal{M}}(\boldsymbol{g})=6^{n}\,[B_{0}(g_{\boldsymbol{\mu}})+B_{3}(g_{\boldsymbol{\mu}})]\,. (77) This model is not independent (because of the self-loop). However, from a modeling perspective, a model with a single pair of c.c. operator could be seen as “independent”, in the sense that: 1) it models (at least partially) one dimension of the system, and 2) it doesn’t encode constraints between different operators. For q non-prime, we extend the notion of independent models to also include models with self-dependent operators that do not create non-trivial constraints (loops) with the other operators of the model. We call these models weakly independent 19 19 19 The notion of weakly independent model is best defined using the definition of length of a module. As (\mathbb{Z}/q\mathbb{Z})^{n} is not a vector space, but a module 47 we introduce the length of a module, a generalization of dimension from vector spaces to modules. The length of a module M , denoted l(M) , is the number of non-zero submodules in the longest possible chain of distinct submodules: 0\subset M_{1}\subset M_{2}\subset\dots\subset M_{l(M)}=M. For a finite set of vectors \boldsymbol{\nu}_{1},\dots,\boldsymbol{\nu}_{K}\in(\mathbb{Z}/q\mathbb{Z})^{n} , we denote by \langle\boldsymbol{\nu}_{1},\dots,\boldsymbol{\nu}_{K}\rangle the submodule of (\mathbb{Z}/q\mathbb{Z})^{n} generated by these vectors, i.e., the set of all (\mathbb{Z}/q\mathbb{Z}) -linear combinations \sum_{k}r_{k}\boldsymbol{\nu}_{k} with r_{k}\in(\mathbb{Z}/q\mathbb{Z}) . Using this notion, a real-valued spin model \mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} is weakly independent if and only if l(\langle\mathcal{M}_{0}\cup\mathcal{M}_{1}\rangle_{gen})=\sum_{\boldsymbol{\mu}\,\in\,\mathcal{M}_{0}\cup\mathcal{M}_{1}}l\bigl(\langle\boldsymbol{\mu}\rangle\bigr). (78) . Corollary 2 . A real-valued weakly independent model (for q non-prime) is a model whose set of loops in Eq. ( 58 ) solely contains the following loops or their combinations: 1) the empty loop; 2) trivial loops due to c.c. operators; 3) trivial loops due to self-dependent operators (i.e., of the type \eta\,\boldsymbol{\mu}=\boldsymbol{0} with \eta2 , one has that \mathcal{M}_{0}=\emptyset and \eta_{\boldsymbol{\mu}}=q for all \boldsymbol{\mu}\in\mathcal{M}_{1} , and we recover Eq. ( 74 ). Finally, substituting Eq. ( 83 ) in Eq. ( 81 ), we obtain: Property 17 . Cluster expansion of the partition around the weakly independent model. Consider a real-valued spin model \mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} . The cluster expansion of the partition function of \mathcal{M} around the weakly independent model is given by: \displaystyle Z_{\mathcal{M}}(\boldsymbol{g})=Z^{wind}_{\mathcal{M}}(\boldsymbol{g})\,\left[\,1+\sum_{(\boldsymbol{\ell}_{0},\boldsymbol{\ell}_{1})\in\mathcal{L}^{cc,s}_{q}(\mathcal{M}_{0},\mathcal{M}_{1})\backslash(\boldsymbol{0},\boldsymbol{0})}\;\prod_{i=1}^{K_{0}}\frac{A_{\ell_{0,i}}}{A_{0}}(g_{\boldsymbol{\mu}_{0,i}})\prod_{j=1}^{K_{1}}\frac{C_{\ell_{1,j}}^{\eta_{j}}}{C_{0}^{\eta_{j}}}(g_{\boldsymbol{\mu}_{1,j}})\,\right]\,, (84) where Z^{wind}_{\mathcal{M}}(\boldsymbol{g}) denotes the partition function of \mathcal{M} computed as if it were weakly independent, which is given by Eq. ( 83 ). The remaining set of loops \mathcal{L}^{cc,s}_{q}(\mathcal{M}_{0},\mathcal{M}_{1}) doesn’t contain any trivial loops (from c.c. operators or self-loops). 3.4 Rank and dimension of a spin model The definition 11 of an independent set of operators allows us to extend the definition of the rank of a spin model, originally introduced in the binary case 9 ; 15 , to q\geq 2 : Definition 14 . Rank of a spin model. The rank of a spin model \mathcal{M} , denoted by \rank(\M) , is the cardinality of the largest linearly independent set of operators in \mathcal{M} . By definition, in an n -spin system, \,\operatorname{rank}(\mathcal{M})\leq n . For example, by definition 12 , the rank of an independent model is equal to the number of operators in the model. For a real-valued independent spin model with q>2 , \mathcal{M}=\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} , the rank of the model is equal to the number of operators in \mathcal{M}_{1} . When q is not prime, the rank of the model is not sufficient to capture the number of dimensions in which the model is embedded. Consider for example a model for q=6 with a single pair of c.c. operators \mathcal{M}=\{\boldsymbol{\mu},-\boldsymbol{\mu}\} verifying the self-dependence relation 3\boldsymbol{\mu}=0 . The rank of this model is zero, but the model is embedded in at least one dimension. This is because the operator \boldsymbol{\mu} lives in one dimension, but doesn’t span the whole (\mathbb{Z}/6\mathbb{Z}) . To clarify this distinction when q is not prime, we introduce the definition of the (embedding) dimension of a q -state spin model. This definition is inspired by the definition of basis of a spin model, which was introduced in the binary case 15 as a minimal set of independent operators that can generate all the operators of the model. Definition 15 . Dimension of a spin model. The dimension of a spin model \mathcal{M} , denoted \dim(\mathcal{M}) , is the cardinality of the minimal independent set of operators that can generate all the operators of the model \mathcal{M} . By definition, in an n -spin system, \,\dim(\mathcal{M})\leq n . For example, for q=6 , for the one-spin model \mathcal{M}=\{\boldsymbol{\mu},-\boldsymbol{\mu}\} with the one-body operator \boldsymbol{\mu}=(2) and its c.c. -\boldsymbol{\mu}=(4) , the set with the single operator \{\boldsymbol{\mu}_{1}=(1)\} is a minimal independent set that can generate all the operators of \mathcal{M} in \mathbb{Z}/6\mathbb{Z} (the operator \boldsymbol{\mu}_{1} is not self-dependent, as oppose to the operators (2) and (4) ). The dimension of \mathcal{M} is therefore \dim(\mathcal{M})=1 . For models without self-dependent operators, any maximal independent set of operators in the model can generate all the operators of the model, which means that the dimension of the model is equal to its rank. This is always the case for models with q=2 , and in general for any q prime, for which there is therefore no need to introduce a distinction between rank and dimension 15 . This is also the case for independent models (complex- or real-valued) at any value of q (prime or not). For models with self-dependent operators (which exist only when q is not prime), the dimension of the model can be larger than its rank. In the example above, \mathcal{M}=\{(2),(4)\} for q=6 , the rank of the model is \rank(\M)=0 , but its dimension is \dim(\mathcal{M})=1 . 3.5 Discussion: Loops as algebraic constraints defining the statistical properties of the spin model The loops of a q -state spin model, defined in Eq. ( 58 ), are linear dependencies between the operators of the model that result from the choice of the model architecture (i.e., which operators are in the model). Equation ( 57 ) connects these structural dependencies, captured by the loop structure on the r.h.s., to the statistical properties of the model, captured by the partition function on the l.h.s. More specifically, the Hessian of the log-partition function corresponds to the Fisher information matrix, a covariance matrix that characterizes how susceptible the model probability distribution is to perturbations around any given value of the parameters. The structural dependencies encoded by the loops \mathcal{L}_{q}(\mathcal{M}) thus ultimately shape the Fisher information matrix, making the model more or less susceptible to changes in the parameters, or, from a modeling perspective, more or less malleable to fit a wide variety of data patterns. This flexibility of a statistical model can be summarized in a single characteristic called the geometric complexity of the model 5 ; 38 , corresponding to the term c_{\mathcal{M}} in Eq. ( 8 ) (when the integral is defined). In the binary case, Ref. 9 explores the impact of the loop structure of a spin model ( 56 ) on the geometric complexity. In summary, equation ( 57 ) draws a useful connection between the statistical properties of a spin model and algebraic properties of its operators, i.e., the linear dependencies between the operators encoded in the loop structure ( 58 ). Equation ( 57 ) describes how these structural dependencies constrain the statistical properties of the model. In the following section, we introduce an algebraic representation of spin models, which will allow for a better characterization of this connection. 4 Gauge transformations (GTs) and equivalence classes of q -state spin models In the binary case, Ref. 9 observed that all the models that have the same loop structure ( 56 ) have the same partition function ( 55 ) up to permutation of their parameters. They introduce bijective transformations of the spin variables (and thus of the state space) that preserve the structure of spin operators, which they call gauge transformations. These transformations map a spin model onto another spin model (with different operators), while keeping the loop structure invariant, therefore preserving the partition function. The transformed spin models can be seen as different representations of the same abstract model. Let us generalize these ideas to q -state spin models. 4.1 Gauge transformations as changes of spin representation Following Ref. 9 , we use the notion of independence between spin operators (see Definition 11 ) to generalize the definition of gauge transformations to systems of q -state spin variables with q>2 . Ref. 15 also introduced a linear algebra formalism for spin models and gauge transformations, which we generalize to larger values of q . Let us start by recalling the definition of independence between spin operators: Definition 16 . Independent set of operators. Consider a system of n q -state spin variables. A set of operators \{\phi^{\boldsymbol{\mu}_{1}},\,\dots,\phi^{\boldsymbol{\mu}_{K}}\} is independent if and only if the set of vectors \mathcal{S}=\{\boldsymbol{\mu}_{1},\,\dots,\boldsymbol{\mu}_{K}\} is linearly independent in (\mathbb{Z}/q\mathbb{Z})^{n} : \displaystyle\forall(r_{k})\in(\mathbb{Z}/q\mathbb{Z})^{K},\;\;\;\;\sum_{k=1}^{K}r_{k}\,\boldsymbol{\mu}_{k}=0\;({\rm mod}\;q)\qquad\Rightarrow\qquad r_{k}=0\;\;\;\;\forall\,k\,. (85) This is equivalent to the set of loops of \mathcal{S} containing only the null vector: \mathcal{L}_{q}(\mathcal{S})=\{\boldsymbol{0}\} . We recall that spin operators are defined in Eq. ( 13 ) as products of the spin variables identified by the vector \boldsymbol{\mu} . Equation ( 85 ) thus means that no operator \phi^{\boldsymbol{\mu}} in the set can be obtained as a product of other operators in the set raised to any power. Moreover, in a system of n spin variables, an independent set of operators can have at most n operators, because there are at most n independent vectors in (\mathbb{Z}/q\mathbb{Z})^{n} . Note that (\mathbb{Z}/q\mathbb{Z})^{n} is not a vector space when q is not prime. However, the definition above in terms of linear independence between elements of (\mathbb{Z}/q\mathbb{Z})^{n} still holds in this case, as well as the other definitions and the linear algebra representation discussed in this section (see the notion of modules in mathematics 47 ). Definition 17 . Gauge transformations (GTs). Consider a system of n q -state spin variables \boldsymbol{s}=(s_{1},\,\dots,\,s_{n}) . A gauge transformation \mathcal{T} is a change of spin basis identified by an ordered set of n independent operators (\phi^{\boldsymbol{\mu}_{1}},\,\dots,\,\phi^{\boldsymbol{\mu}_{n}}) , where the new basis variables \boldsymbol{s}^{\prime}=(s_{1}^{\prime},\,\dots,\,s_{n}^{\prime}) are defined as: \displaystyle\mathcal{T}:\boldsymbol{s}\rightarrow\begin{cases}s_{1}^{\prime}=\phi^{\boldsymbol{\mu}_{1}}(\boldsymbol{s})\\ \;\;\cdots\\ s_{n}^{\prime}=\phi^{\boldsymbol{\mu}_{n}}(\boldsymbol{s})\end{cases}\,. (86) The transformation can equivalently be written in terms of the discrete variables \boldsymbol{\alpha}=(\alpha_{1},\,\dots,\,\alpha_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} , where each \alpha_{j} is the color of the spin s_{j} . Under the gauge transformation \mathcal{T} above, the new variables \boldsymbol{\alpha}^{\prime}=(\alpha_{1}^{\prime},\,\dots,\,\alpha_{n}^{\prime})\in(\mathbb{Z}/q\mathbb{Z})^{n} are defined as: \displaystyle{\rm for}\;{\rm all}\;j\in\{1,\cdots,n\},\qquad\alpha_{j}^{\prime}=\boldsymbol{\alpha}\cdot\boldsymbol{\mu}_{j}\,, (87) where each variable \alpha_{j}^{\prime} is the color of the spin s_{j}^{\prime} and where the scalar product is taken in (\mathbb{Z}/q\mathbb{Z})^{n} . Figure 6 .a gives an example of a gauge transformation for a spin model with q=3 . Note that self-dependent operators (operators \boldsymbol{\mu} for which there exists a scalar c\in(\mathbb{Z}/q\mathbb{Z}) such that c\boldsymbol{\mu}=\boldsymbol{0} ) cannot contribute to a set of independent operators, and therefore, they cannot be used to define a GT. Using the definition of spin operators in Eq. ( 14 ), it is straightforward to check that the new variables s_{j}^{\prime} defined by the transformation ( 86 ) are indeed still q -state spin variables ( 10 ): \displaystyle s_{j}^{\prime}=\phi^{\boldsymbol{\mu}_{j}}(\boldsymbol{s})=z_{q}^{\,\boldsymbol{\alpha}\cdot\boldsymbol{\mu}_{j}}=z_{q}^{\,\alpha_{j}^{\prime}}\,,\qquad{\rm where}\;\;\alpha_{j}^{\prime}=\boldsymbol{\alpha}\cdot\boldsymbol{\mu}_{j} (88) are the corresponding colors. This also proves the expression ( 87 ) of the GT in terms of the colors. Because the set of n vectors (\boldsymbol{\mu}_{1},\,\dots,\,\boldsymbol{\mu}_{n}) are linearly independent, they form a new basis of (\mathbb{Z}/q\mathbb{Z})^{n} , and Eq. ( 87 ) simply re-writes the states of \boldsymbol{\alpha} into this new basis. Hence, GTs written for the variables \boldsymbol{\alpha} correspond to linear basis transformations in (\mathbb{Z}/q\mathbb{Z})^{n} , which can be identified as the automorphisms of (\mathbb{Z}/q\mathbb{Z})^{n} . Property 18 . Matrix representation of gauge transformations. For convenience, the gauge transformation in Eq. ( 87 ) can be written as the vector-matrix product over (\mathbb{Z}/q\mathbb{Z}) 15 : \displaystyle\boldsymbol{\alpha}^{\prime}=\boldsymbol{\alpha}\,\boldsymbol{T}\,, (89) where \boldsymbol{\alpha}=(\alpha_{1},\,\dots,\,\alpha_{n}) and \boldsymbol{\alpha}^{\prime}=(\alpha_{1}^{\prime},\,\dots,\,\alpha_{n}^{\prime}) are two row vectors containing respectively the states of the original variables \alpha_{j} and of the new variables \alpha_{j}^{\prime} , and \boldsymbol{T}=(\boldsymbol{\mu}_{1},\,\dots,\,\boldsymbol{\mu}_{n}) is an n\times n -matrix whose columns are the linearly independent vectors \boldsymbol{\mu}_{j} defining the gauge transformation. When performing the matrix product over (\mathbb{Z}/q\mathbb{Z}) in Eq. ( 89 ), the elements of the resulting vector are taken modulo q . The n columns of \boldsymbol{T} being linearly independent in (\mathbb{Z}/q\mathbb{Z})^{n} means that \boldsymbol{T} is invertible in (\mathbb{Z}/q\mathbb{Z})^{n} . Multiplying Eq. ( 89 ) on both side by the inverse matrix \boldsymbol{T}^{-1} allows one to recover the original variables from the transformed ones, thus defining the inverse gauge transformation (also confirming that GTs are indeed bijective). Property 19 . Inverse gauge transformation. Gauge transformations (GTs) are bijective. Following a GT, the original variables \boldsymbol{\alpha} can be recovered from the transformed variables \boldsymbol{\alpha}^{\prime} using: \displaystyle\boldsymbol{\alpha}=\boldsymbol{\alpha}^{\prime}\,\boldsymbol{T}^{-1}\,, (90) where \boldsymbol{T}^{-1} is the inverse of the matrix representation \boldsymbol{T} of the GT. In the following, we will often denote by \boldsymbol{b}=(\phi^{\boldsymbol{\mu}_{1}},\,\dots,\,\phi^{\boldsymbol{\mu}_{n}}) the set of n independent operators used to define the new basis, by \mathcal{T}_{b} the corresponding gauge transformation, and by \boldsymbol{T}_{\boldsymbol{b}} its matrix representation. The change of basis will then be denoted by \boldsymbol{s}^{\prime}=\boldsymbol{b}(\boldsymbol{s}) or, equivalently, by \boldsymbol{\alpha}^{\prime}=\boldsymbol{\alpha}\,\boldsymbol{T}_{\boldsymbol{b}} . Similarly, we will denote by \mathcal{T}_{\boldsymbol{b}}^{-1} the inverse GT, which is represented by the inverse matrix \boldsymbol{T}_{\boldsymbol{b}}^{\,-1} . The columns of \boldsymbol{T}_{\boldsymbol{b}}^{\,-1} identify n independent vectors \boldsymbol{\mu}_{j}^{\prime} , which correspond to the operators defining the basis of the inverse GT, \,\boldsymbol{b}^{-1}=(\phi^{\boldsymbol{\mu}_{1}^{\prime}},\,\dots,\,\phi^{\boldsymbol{\mu}_{n}^{\prime}}) . For a system of n q -state spin variables, each choice of gauge transformation \boldsymbol{s}^{\prime}=\boldsymbol{b}(\boldsymbol{s}) can be performed on the vector of discrete variables \boldsymbol{\alpha} by multiplying it with the corresponding invertible n\times n -matrix \boldsymbol{T}_{\boldsymbol{b}} in (\mathbb{Z}/q\mathbb{Z})^{n} , as described in Property 18 . Reciprocally, the columns of each invertible n\times n -matrix \boldsymbol{T} in (\mathbb{Z}/q\mathbb{Z})^{n} uniquely identify n linearly independent vectors \boldsymbol{\mu}_{i}\in(\mathbb{Z}/q\mathbb{Z})^{n} , \boldsymbol{T}=(\boldsymbol{\mu}_{1},\,\dots,\,\boldsymbol{\mu}_{n}) , and therefore uniquely identify a gauge transformation. It is then easy to see that GTs, when written in terms of the variables \boldsymbol{\alpha}\in(\mathbb{Z}/q\mathbb{Z})^{n} , are the automorphisms of (\mathbb{Z}/q\mathbb{Z})^{n} (i.e., corresponding to all possible invertible n\times n -matrices over (\mathbb{Z}/q\mathbb{Z}) ). Property 20 . Consider a system of n q -state spins characterized by the discrete color variables \boldsymbol{\alpha}=(\alpha_{1},\dots,\alpha_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} . The gauge transformations defined for spin systems in Definition 17 are the automorphisms of the state space of the variables \boldsymbol{\alpha} , i.e., they are the automorphisms of the cyclic group (\mathbb{Z}/q\mathbb{Z})^{n} : \displaystyle\mathcal{G}_{q}(n)=Aut[(\mathbb{Z}/q\mathbb{Z})^{n}]\,, (91) where \mathcal{G}_{q}(n) denotes the set of all gauge transformations. Property 21 . Total number of GTs. It follows that, for q prime, the number of possible gauge transformations is: \displaystyle\textrm{for}\;q\;\textrm{prime},\;\qquad|\mathcal{G}_{q}(n)|=\prod_{i=0}^{n-1}(q^{n}-q^{i})\,. (92) For q not prime, let’s consider the prime factorization q=\prod_{k=1}^{K}p_{k}^{\,m_{k}} , where the p_{k} ’s are prime numbers and the m_{k} ’s are their multiplicity. The number of automorphisms of (\mathbb{Z}/q\mathbb{Z})^{n} is given by: \displaystyle\textrm{for}\;q\;\textrm{non prime},\;\qquad|\mathcal{G}_{q}(n)|=\prod_{k=1}^{K}p_{k}^{\,(m_{k}-1)n^{2}}\,\prod_{i=0}^{n-1}(p_{k}^{\,n}-p_{k}^{\,i})\,. (93) When q is prime, the number of GTs ( 92 ) is straightforward to compute: after choosing the i first independent operators \boldsymbol{\mu}_{i} of the basis in Eq. ( 86 ), there are exactly (q^{n}-q^{i}) possibilities to choose the (i+1) -th operator \boldsymbol{\mu}_{i+1} such that it is independent from the i operators already chosen. This is because the set of i independent vectors \boldsymbol{\mu} already chosen can generate q^{i} different vectors (and thus, different operators) through linear combinations in (\mathbb{Z}/q\mathbb{Z})^{n} , and \boldsymbol{\mu}_{i+1} cannot be chosen among them. If q is not prime, then for some operators \boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{n} there exists a strictly positive integer c2 andprime).\begin{Definition}{\bf Reduced representation of real-valued spin models.} Consider a real-valued $q$-state spin model $\mathcal{M}$. Using the decomposition of Definition~\ref{def:M:M0-M1}, $\mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*}$, we defined the reduced model $\mathcal{M}_{r}=\mathcal{M}_{0}\cup\mathcal{M}_{1}$, such that $\mathcal{M}=\mathcal{M}_{r}\cup\mathcal{M}_{r}^{*}$, where the operators in $\mathcal{M}_{r}^{*}$ are the c.c.~of the operators in $\mathcal{M}_{r}$ (note that the operators of $\mathcal{M}_{0}$ are both in $\mathcal{M}_{r}$ and $\mathcal{M}_{r}^{*}$). The reduced matrix representation of $\mathcal{M}$ is the matrix whose column are the operators of $\mathcal{M}_{r}$. The choice of the reduced representation $\mathcal{M}_{r}$ for a given model $\mathcal{M}$ is not unique. \end{Definition}\par Besidessimplifyingtherepresentationofreal-valuedspinmodels,thereducedmatrixrepresentationcanalsobeusedforthegaugetransformationofthesemodels,thankstothefollowingproperty(seeproofinApp.~\ref{App:M_r}):\begin{Property}Conjugate operators $(\boldsymbol{\mu},-\boldsymbol{\mu})$ stay conjugate under a GT: $\,\mathcal{T}[-\boldsymbol{\mu}]=-\mathcal{T}[\boldsymbol{\mu}]$. \end{Property}\noindent Therefore,foreachconjugatepair ( μ ,- μ ) ,theGToftheoperatornon-representedinthereducedmodel,let^{\prime}ssay - μ ,istheconjugateoftheGToftherepresentedoperator~ μ .Manipulationsofthemodelsuchasgaugetransformationscanthusbedirectlyperformedonthereducedmodel,andtheGTofthefullmodel M ’= T [ M ] canberecoveredfromtheGTofthereducedmodel M _r’= T [ M _r] ,using M ’= M _r’∪ M _r’^* .\begin{Property}Consider a model $\mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*}$ with reduced representation $\mathcal{M}_{r}=\mathcal{M}_{0}\cup\mathcal{M}_{1}$, and denote $\mathcal{M}^{\prime}=\mathcal{T}[\mathcal{M}]$ the transformation of $\mathcal{M}$ under a given GT $\mathcal{T}$. Using the reduced representation $\mathcal{M}_{r}$, the transformed model $\mathcal{M}^{\prime}$ can be computed as $\mathcal{M}^{\prime}=\mathcal{M}_{r}^{\prime}\cup\mathcal{M}_{r}^{\prime\,*}$, where $\mathcal{M}_{r}^{\prime}=\mathcal{T}[\mathcal{M}_{r}]$ is the gauge transformation of the reduced model. \end{Property}\noindent UsingthedecompositionofDefinition~\ref{def:M:M0-M1}forthetransformedmodel, M ’= M _0’∪ M _1’∪ M _1’^* ,Property~\ref{ppty:GT:cc-op}alsoimpliesthat T [ M _0]= M _0’ (i.e.,forall μ _0∈ M _0 ,theoperator μ _0’= T [ μ _0] isitsownconjugate)and T [ M _1∪ M _1’]= M _1’∪ M _1’^ * (seeApp.~\ref{App:M_r}).\par 4.5 Algebraic representation of q -state spin models As hinted at by the matrix representations introduced above, spin models can be studied from a linear algebra perspective. In this section, we formalize this framework by introducing a linear map representation of spin models. Definition 22 . Linear map representation of spin models. Consider a system of n discrete variables (\alpha_{1},\dots,\alpha_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} and a q -state spin model \mathcal{M} for this system, specified by the choice of K operators, \mathcal{M}=\{\boldsymbol{\mu}_{1},\dots,\boldsymbol{\mu}_{K}\}\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*} . The model \mathcal{M} can be represented as a linear map f_{\mathcal{M}} from (\mathbb{Z}/q\mathbb{Z})^{K} to (\mathbb{Z}/q\mathbb{Z})^{n} which defines each operator of the model in terms of the state variables. We denote (\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{K}) a basis of the domain \mathcal{U}=(\mathbb{Z}/q\mathbb{Z})^{K} , which can be thought of as the model’s space; we associate each of these basis elements with one of the K operators of the model \mathcal{M} . We denote (\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{n}) a basis of the codomain \mathcal{V}=(\mathbb{Z}/q\mathbb{Z})^{n} , which can be thought of as the space of the spin system, and associate each of these basis elements with one of the n discrete (color) variables of the system. The linear map f_{\mathcal{M}} is defined by specifying the following image for each basis element of \mathcal{U} : \displaystyle\textrm{for all }k\in\{1,\dots,K\}\,,\qquad\qquad f_{\mathcal{M}}(\boldsymbol{u}_{k})=\sum_{j=1}^{n}\mu_{k}^{(j)}\,\boldsymbol{v}_{j}=\boldsymbol{\mu}_{k}\,,\qquad\qquad (103) where the coefficient \mu_{k}^{(j)} corresponds to the j -th element of the vector \boldsymbol{\mu}_{k}\in(\mathbb{Z}/q\mathbb{Z})^{n} defining the k -th operator of \mathcal{M} . Here the vector \boldsymbol{\mu}_{k}=(\mu_{k}^{(1)},\dots,\mu_{k}^{(n)}) is considered as an element of the codomain. Following this approach, the matrix representation of the linear map f_{\mathcal{M}} defined in Eq. ( 103 ) corresponds precisely to the n\times K -matrix \boldsymbol{M} introduced in Definition 20 as the matrix representation of the spin model \mathcal{M} . Note that (\mathbb{Z}/q\mathbb{Z}) is a vector space when q is prime, it is a module otherwise. The linear map representation is valid in both cases. For example, the model \mathcal{M} shown in Fig. 6 .a top, with K=10 operators over n=3 spins, corresponds to the following linear map: f_{\mathcal{M}}:(\mathbb{Z}/3\mathbb{Z})^{10}\to(\mathbb{Z}/3\mathbb{Z})^{3} , \displaystyle\begin{cases}\;f_{\mathcal{M}}(\boldsymbol{u}_{1})=\boldsymbol{\mu}_{1}=\boldsymbol{v}_{1}\,;\qquad&f_{\mathcal{M}}(\boldsymbol{u}_{2})=\boldsymbol{\mu}_{2}=2\boldsymbol{v}_{1}\\ \;f_{\mathcal{M}}(\boldsymbol{u}_{3})=\boldsymbol{\mu}_{3}=\boldsymbol{v}_{2}\,;\qquad&f_{\mathcal{M}}(\boldsymbol{u}_{4})=\boldsymbol{\mu}_{4}=2\boldsymbol{v}_{2}\\ \;f_{\mathcal{M}}(\boldsymbol{u}_{5})=\boldsymbol{\mu}_{5}=\boldsymbol{v}_{1}+\boldsymbol{v}_{2}\,;\qquad&f_{\mathcal{M}}(\boldsymbol{u}_{6})=\boldsymbol{\mu}_{6}=2\boldsymbol{v}_{1}+2\boldsymbol{v}_{2}\\ \;f_{\mathcal{M}}(\boldsymbol{u}_{7})=\boldsymbol{\mu}_{7}=\boldsymbol{v}_{1}+2\boldsymbol{v}_{3}\,;\;\qquad&f_{\mathcal{M}}(\boldsymbol{u}_{8})=\boldsymbol{\mu}_{8}=2\boldsymbol{v}_{1}+\boldsymbol{v}_{3}\\ \;f_{\mathcal{M}}(\boldsymbol{u}_{9})=\boldsymbol{\mu}_{9}=\boldsymbol{v}_{2}+\boldsymbol{v}_{3}\,;\qquad\qquad&f_{\mathcal{M}}(\boldsymbol{u}_{10})=\boldsymbol{\mu}_{10}=2\boldsymbol{v}_{2}+2\boldsymbol{v}_{3}\end{cases}\,, (104) whose matrix representation is the same as the matrix representation \boldsymbol{M} of the spin model given in Eq. ( 4.4 ) (we labeled the operators in the same way in Eq. ( 104 ) and ( 4.4 )). Figure 7 gives an illustration of the linear map representation of q -state spin models. The state of the system is characterized by the state of the n discrete random variables \alpha_{j} (colors of the spins) and is represented in the system space \mathcal{V} by the random vector \boldsymbol{\alpha}=\sum_{j=1}^{n}\alpha_{j}\boldsymbol{v}_{j} , corresponding to the coordinate vector \boldsymbol{\alpha}=(\alpha_{1},\cdots,\alpha_{n}) . The state of the model is characterized by the state of the K operators of the model. We denote by m_{k}\in(\mathbb{Z}/q\mathbb{Z}) the color of the k -th spin operator (the state of this operator is thus z_{q}^{m_{k}} ). With this notation, the state of the model is then described by the K discrete random variables m_{k} and is represented in the model space \mathcal{U} by the random vector \boldsymbol{m}=\sum_{k=1}^{K}m_{k}\boldsymbol{u}_{k}=(m_{1},\cdots,m_{K}) . Using the linear map f_{\mathcal{M}} , each operator \boldsymbol{u}_{k}\in\mathcal{U} of the model \mathcal{M} is given a representation \boldsymbol{\mu}_{k}\in\mathcal{V} in the system space. The state m_{k} of the k -th operator when the system is in a state \boldsymbol{\alpha} is then given by the dot product m_{k}=\boldsymbol{\alpha}\cdot\boldsymbol{\mu}_{k} in \mathcal{V} (because \phi^{\boldsymbol{\mu}_{k}}(\boldsymbol{\alpha})=z_{q}^{\boldsymbol{\alpha}\cdot\boldsymbol{\mu}_{k}}=z_{q}^{m_{k}} ). We can thus obtain the state of the model \boldsymbol{m}\in\mathcal{U} when the system is in the state \boldsymbol{\alpha}\in\mathcal{V} by the vector-matrix product \boldsymbol{m}=\boldsymbol{\alpha}\,\boldsymbol{M} over (\mathbb{Z}/q\mathbb{Z}) , where \boldsymbol{\alpha} is considered as a row vector and \boldsymbol{M} is the matrix representation of f_{\mathcal{M}} . In an n -spin system, all the statistical properties of the system are captured by the ensemble averages of each the (q^{n}-1) spin operators (i.e., all the high-order moments). In this framework, each spin operator whose statistics is constrained by the model has two representations: one in the system space \mathcal{V} and one in the model space \mathcal{U} . In the system space , any spin operator can be written as a product of spin variables (monomials). This product corresponds to a linear combination of the color variables \alpha_{i} , which is represented by a vector \boldsymbol{\mu}\in\mathcal{V} . The random variable \boldsymbol{\alpha}\cdot\boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z}) , obtained from the dot product of \boldsymbol{\mu} with the random state vector \boldsymbol{\alpha} , then characterizes the state of the operator \phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})=z_{q}^{\boldsymbol{\alpha}\cdot\boldsymbol{\mu}} when the system is in the state \boldsymbol{\alpha} . In the model space , any spin operator that can be written as a product of operators of the model (monomials over the operators) is represented as a vector \boldsymbol{u}=\sum_{k}u_{k}\boldsymbol{u}_{k}=(u_{1},\dots,u_{K})\in\mathcal{U} . For example, the vector \boldsymbol{u}=\boldsymbol{u}_{1}+2\boldsymbol{u}_{2}\in\mathcal{U} represents the spin operator \phi^{\boldsymbol{u}}(\boldsymbol{m})=\phi^{\boldsymbol{u_{1}}}(\boldsymbol{m})[\phi^{\boldsymbol{u_{2}}}(\boldsymbol{m})]^{2} , where the operators \phi^{\boldsymbol{u_{k}}}(\boldsymbol{m}) are the operators of the model. The random variable \boldsymbol{m}\cdot\boldsymbol{u}\in(\mathbb{Z}/q\mathbb{Z}) , obtained from the dot product of \boldsymbol{u} with the random state vector \boldsymbol{m} , then characterizes the state of the operator \phi^{\boldsymbol{u}}(\boldsymbol{m})=z_{q}^{\boldsymbol{u}\cdot\boldsymbol{m}} when the model is in the state \boldsymbol{m} . For a chosen model \mathcal{M} , the linear map f_{\mathcal{M}} associates each operator represented by \boldsymbol{u}=\sum_{k=1}^{K}u_{k}\boldsymbol{u}_{k}\in\mathcal{U} in model space to a representation \boldsymbol{\mu}=f_{\mathcal{M}}(\boldsymbol{u})=\sum_{k=1}^{K}u_{k}\boldsymbol{\mu}_{k}\in\mathcal{V} in the system space. The state of the spin operator can then be equivalently written in model space as \boldsymbol{m}\cdot\boldsymbol{u}=\sum_{k}m_{k}u_{k} and in system space as \boldsymbol{\alpha}\cdot\boldsymbol{\mu}=\sum_{k}u_{k}\boldsymbol{\alpha}\cdot\boldsymbol{\mu}_{k}=\sum_{k}u_{k}m_{k} (i.e., \phi^{\boldsymbol{u}}(\boldsymbol{m})=\phi^{f_{\mathcal{M}}(\boldsymbol{u})}(\boldsymbol{\alpha}) ). If the rank of the model is smaller than n , then not all spin operators in \mathcal{V} have a representation in the model space \mathcal{U} . The operators that can be decomposed in \mathcal{U} are those whose statistical properties are controlled by the statistics of the operators of the model (namely the relevant statistics). The other operators are given a uniform distribution in the model 22 22 22 For example, for the model \mathcal{M}=\{\phi^{\boldsymbol{\mu}_{1}}(\boldsymbol{s})=s_{1},\,\phi^{\boldsymbol{\mu}_{2}}(\boldsymbol{s})=s_{1}s_{2}s_{3}\} with q=2 , the spin operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=s_{2} cannot be obtained as a product of operators of the model, but the operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=s_{2}s_{3} can. . Different operators \boldsymbol{u}\in\mathcal{U} can be mapped by f_{\mathcal{M}} to the same operator \boldsymbol{\mu}\in\mathcal{V} , which means that the same spin operator (expressed in terms of the system’s variables \boldsymbol{\alpha} ) can be decomposed in different ways over the operators of the model 23 23 23 For example, for the model \mathcal{M}=\{\phi^{\boldsymbol{\mu}_{1}}(\boldsymbol{s})=s_{1},\,\phi^{\boldsymbol{\mu}_{2}}(\boldsymbol{s})=s_{2},\,\phi^{\boldsymbol{\mu}_{3}}(\boldsymbol{s})=s_{3},\,\phi^{\boldsymbol{\mu}_{4}}(\boldsymbol{s})=s_{1}s_{2}s_{3}\} with q=2 , the operator \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=s_{1}s_{2} can be decomposed as \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=\phi^{\boldsymbol{\mu}_{1}}(\boldsymbol{s})\phi^{\boldsymbol{\mu}_{2}}(\boldsymbol{s}) or as \phi^{\boldsymbol{\mu}}(\boldsymbol{s})=\phi^{\boldsymbol{\mu}_{3}}(\boldsymbol{s})\phi^{\boldsymbol{\mu}_{4}}(\boldsymbol{s}) . . Finally, the operators \boldsymbol{u}\in\mathcal{U} that are mapped to \boldsymbol{0}\in\mathcal{V} correspond to the loops of the model (because they identify products of operators of the model that are equal to identity in the system space). Gauge transformations are changes of basis of the state space of the system, which, in this framework, correspond to automorphisms of the codomain \mathcal{V}=(\mathbb{Z}/q\mathbb{Z})^{n} (see Fig. 7 ). These automorphisms can be represented by invertible n\times n -matrices over (\mathbb{Z}/q\mathbb{Z}) and the GT of a model is then obtained by the matrix product previously described in property 22 . Definition 23 . Gauge transformations. GTs are automorphisms of the codomain of the linear map f_{\mathcal{M}} representing the spin model \mathcal{M} . Figure 7: Illustration: Representation of q -state spin models as linear maps. We consider a system with n q -state spin variables and a spin model \mathcal{M} with K operators. The space \mathcal{V}=(\mathbb{Z}/q\mathbb{Z})^{n} (on the right) is the system space, in which each of the n basis elements is associated with one of the spin variables. The state of the system is then represented by the random vector \boldsymbol{\alpha}=(\alpha_{1},\dots,\alpha_{n})\in\mathcal{V} , where \alpha_{j} is the color of the j -th spin, and a spin operator is represented as a vector \boldsymbol{\mu}\in\mathcal{V} , which gives the decomposition of the operator in terms of the variables of the system. The space \mathcal{U}=(\mathbb{Z}/q\mathbb{Z})^{K} (on the left) is the model space, in which each of the K basis elements is associated with one of the operators of the model (which are the variables of the models). The state of the model is then represented by the random vector \boldsymbol{m}=(m_{1},\dots,m_{K})\in\mathcal{U} , where m_{k} is the color of the k -th operator, \phi^{\boldsymbol{u}_{k}}(\boldsymbol{m})=z_{q}^{m_{k}} , and each spin operator that can be decomposed over the operators of the model is represented by a vector \boldsymbol{u}\in\mathcal{U} . A model \mathcal{M} is represented by a linear map f_{\mathcal{M}} that associates each operator represented by \boldsymbol{u}\in\mathcal{U} in model space to a representation \boldsymbol{\mu}=f_{\mathcal{M}}(\boldsymbol{u})\in\mathcal{V} in system space. The map f_{\mathcal{M}} is defined in Eq. ( 103 ) by specifying the image \boldsymbol{\mu}_{k}=f_{\mathcal{M}}(\boldsymbol{u}_{k})\in\mathcal{V} of each basis vector \boldsymbol{u}_{k}\in\mathcal{U} . Gauge transformations \mathcal{T} are automorphisms of \mathcal{V} . Loops of \mathcal{M} correspond to the vectors \boldsymbol{\ell}\in\mathcal{U} whose image is the null vector f_{\mathcal{M}}(\boldsymbol{\ell})=\boldsymbol{0}\in\mathcal{V} . Using this framework, we can identify several properties of linear maps that are useful for characterizing spin models, such as the rank of the map and the properties of its kernel. The notion of rank of a spin model \mathcal{M} was already introduced in Definition 14 as the cardinality of the largest linearly independent set of operators in \mathcal{M} . This is the same as the rank of the matrix representation of \mathcal{M} , and therefore it coincides with the rank of the linear map associated with \mathcal{M} . The kernel of a linear map is the set of all the vectors in the domain that are mapped to the zero vector in the codomain (as illustrated by the vector \boldsymbol{\ell} in Fig. 7 ). For example, the vector \boldsymbol{u}_{1}+\boldsymbol{u}_{3}+2\boldsymbol{u}_{5} is in the kernel of the map f_{\mathcal{M}} defined in Eq. ( 104 ), as its image is the zero vector: \displaystyle f_{\mathcal{M}}(\boldsymbol{u}_{1}+\boldsymbol{u}_{3}+2\boldsymbol{u}_{5}) \displaystyle=\boldsymbol{\mu}_{1}+\boldsymbol{\mu}_{3}+2\boldsymbol{\mu}_{5}=\boldsymbol{v}_{1}+\boldsymbol{v}_{2}+2(\boldsymbol{v}_{1}+\boldsymbol{v}_{2})=\boldsymbol{0}\,. (105) Here, we can recognize one of the loops of \mathcal{M} , which is the first loop represented in Fig. 6 .b (top left loop). We recall that a loop of a model with operators \{\boldsymbol{\mu}_{k}\}_{1\leq k\leq K} is a vector \boldsymbol{\ell}\in(\mathbb{Z}/q\mathbb{Z})^{K} that verifies that \sum_{k=1}^{K}\ell_{k}\boldsymbol{\mu}_{k}=\boldsymbol{0} , where \ell_{k} denotes the k -th coefficient of \boldsymbol{\ell} (see Eq. ( 58 )). Labeling the operators in the same order as in Eq. ( 104 ), the loop above can be represented as the coordinate vector \boldsymbol{\ell}=\boldsymbol{u}_{1}+\boldsymbol{u}_{3}+2\boldsymbol{u}_{5}=(1,0,1,0,2,0,0,0,0,0) in \mathcal{U} . More generally, the loops of a model \mathcal{M} are precisely the elements of the kernel of f_{\mathcal{M}} ; they identify dependence relations in \mathcal{V} between the operators \boldsymbol{\mu}_{k} of \mathcal{M} , i.e., between the images of the basis elements \boldsymbol{u}_{k} . Let’s provide a more formal proof of this last point. Proof. Consider a spin model \mathcal{M}=\{\boldsymbol{\mu}_{1},\dots,\boldsymbol{\mu}_{K}\}\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*} with K operators. We recall that the set of loops of \mathcal{M} is defined in Eq. ( 58 ) as: \displaystyle\mathcal{L}_{q}(\mathcal{M})=\bigg\{\boldsymbol{\ell}\in(\mathbb{Z}/q\mathbb{Z})^{K}\;\Big|\;\sum_{k=1}^{K}\ell_{k}\,\boldsymbol{\mu}_{k}=\boldsymbol{0}\bigg\}\,, (106) where \ell_{k} denotes the k -th coefficient of \boldsymbol{\ell} . Using the matrix representation of the model \boldsymbol{M}=(\boldsymbol{\mu}_{1},\dots,\boldsymbol{\mu}_{K}) , in which the vectors \boldsymbol{\mu}_{k} are the columns of the matrix (see Definition 20 ), and viewing \boldsymbol{\ell} as a column vector, we can rewrite \mathcal{L}_{q}(\mathcal{M}) in the following form: \displaystyle\mathcal{L}_{q}(\mathcal{M})=\Big\{\boldsymbol{\ell}\in(\mathbb{Z}/q\mathbb{Z})^{K}\;\Big|\;\boldsymbol{M}\,\boldsymbol{\ell}=\boldsymbol{0}\Big\}=\ker(\boldsymbol{M})\;. (107) Because \boldsymbol{M} is also the matrix representation of the linear map f_{\mathcal{M}} associated with the model \mathcal{M} , Eq. ( 107 ) above means that the set of loops of \mathcal{M} corresponds to the kernel of f_{\mathcal{M}} . ∎ Property 25 . Spin models \mathcal{M} inherit properties of their linear map representation f_{\mathcal{M}} in Def. 22 : – the matrix representation of a model in Definition 20 is the matrix representation of the map; – the rank of a model in Definition 14 is the rank of the map, \rank(\M)=\rank(f_{\M}) ; – the set of loops of a model defined in Eq. ( 58 ) is the kernel of the map, \mathcal{L}_{q}(\mathcal{M})=\ker(f_{\mathcal{M}}) . Figure 6 .b shows the loops of the spin model \mathcal{M} taken as an example above. In this model, operators are included by conjugate pairs, just like for real-valued spin models (see Definition 5 ). For clarity in Fig. 6 , we only displayed the elements of the reduced set of loops \mathcal{L}^{cc}_{q}(\mathcal{M}) defined for real-valued spin models in Eq. ( 68 ); in short, we didn’t represent trivial loops resulting from complex conjugate operators (of the type \boldsymbol{\mu}_{i}+\boldsymbol{\mu}_{j}=\boldsymbol{0} ) nor their combinations with other loops. For example, the first loop in the top left of the figure corresponds to \boldsymbol{\mu}_{1}+\boldsymbol{\mu}_{3}+2\boldsymbol{\mu}_{5}=\boldsymbol{v}_{1}+\boldsymbol{v}_{2}+2(\boldsymbol{v}_{1}+\boldsymbol{v}_{2})=\boldsymbol{0} in (\mathbb{Z}/3\mathbb{Z})^{n} . Considering all linear combinations of this loop with the trivial loop \boldsymbol{\mu}_{1}+\boldsymbol{\mu}_{2}=\boldsymbol{0} from the c.c. operators \boldsymbol{\mu}_{1} and \boldsymbol{\mu}_{2} , we also get the following loops: 2\boldsymbol{\mu}_{1}+\boldsymbol{\mu}_{2}+\boldsymbol{\mu}_{3}+2\boldsymbol{\mu}_{5}=\boldsymbol{0} , 2\boldsymbol{\mu}_{2}+\boldsymbol{\mu}_{3}+2\boldsymbol{\mu}_{5}=\boldsymbol{0} , and \boldsymbol{\mu}_{2}+2\boldsymbol{\mu}_{3}+\boldsymbol{\mu}_{5}=\boldsymbol{0} , which are not represented in Fig. 6 .b. Note that the choice of the loops in \mathcal{L}^{cc}_{q}(\mathcal{M}) is not unique, but it is fully determined by the choice of the operators in the reduced model representation \mathcal{M}_{r} . The reduced loop structure \mathcal{L}_{q}^{cc}(\mathcal{M}) of a real-valued spin model can be also related to the kernel of the model’s reduced representation (see Definition ). More precisely, for real-valued spin models that can be written under the form 24 24 24 This is always the case when q is prime and larger than 2 . \mathcal{M}=\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} with the decomposition of Definition 10 (i.e., for which \mathcal{M}_{0}=\emptyset – such as the model taken as an example above), the reduced set of loops of \mathcal{M} , excluding trivial loops due to c.c. operators, is equal to the kernel of its reduced matrix representation \boldsymbol{M}_{1} : \mathcal{L}_{q}^{cc}(\mathcal{M})=\mathcal{L}_{q}(\mathcal{M}_{1})=\ker(\boldsymbol{M}_{1}) , where \boldsymbol{M}_{1} is a matrix whose columns are the operators in \mathcal{M}_{1} (see proof in App. C.3 ). Finally, because \mathcal{L}_{q}(\mathcal{M})=\ker(f_{\mathcal{M}}) , the loop structure of a spin model inherits the properties of kernels of linear maps. In particular if q is prime, the kernel of f_{\mathcal{M}} is a vector subspace of \mathcal{U}=(\mathbb{Z}/q\mathbb{Z})^{K} of dimension \dim(\ker(f_{\mathcal{M}}))=K-\rank(f_{\M}) , where K=|\mathcal{M}| ; we denote this dimension \lambda . Consequently, all the elements of \ker(f_{\mathcal{M}}) can be generated by a set of \lambda linearly independent vectors in \ker(f_{\mathcal{M}}) , and the cardinality of \ker(f_{\mathcal{M}}) is then q^{\lambda} . This generalizes to q>2 and prime the result found in the binary case 9 that the set of loops of a binary spin model has the structure of an Abelian group generated by \lambda independent loops, where \lambda=K-\rank(\M) with K=|\mathcal{M}| . Property 26 . For q prime, the set of loops \mathcal{L}_{q}(\mathcal{M}) of a spin model \mathcal{M} with K=|\mathcal{M}| operators is a vector subspace of (\mathbb{Z}/q\mathbb{Z})^{K} of dimension \lambda=K-\rank(\M) . It is generated by \lambda independent loops, and its cardinality is |\mathcal{L}_{q}(\mathcal{M})|=q^{\lambda} . For real-valued spin models with q prime, the model can be written under the form \mathcal{M}=\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} ( \mathcal{M}_{0}=\emptyset for q prime), where \mathcal{M}_{1} is the reduce representation \mathcal{M} . Similarly, the reduced loop structure \mathcal{L}^{cc}_{q}(\mathcal{M}) can be written as the kernel of the reduced model \boldsymbol{M}_{1} , which is also a vector subspace of \mathcal{U} of dimension \lambda_{1}=\dim(\ker(\boldsymbol{M}_{1}))=|\mathcal{M}_{1}|-\rank(\M_1) . All the loops of \mathcal{L}^{cc}_{q}(\mathcal{M}) can be generated by \lambda_{1} independent loops and the number of loops in \mathcal{L}^{cc}_{q}(\mathcal{M}) is thus |\mathcal{L}^{cc}_{q}(\mathcal{M}_{1})|=q^{\lambda_{1}} . For example, the model \mathcal{M} in Fig. 6 has nine loops in the reduced set \mathcal{L}^{cc}_{3}(\mathcal{M}) (including the empty loop and excluding trivial loops due to c.c. operators). They are all generated by two independent loops, because \lambda_{1}=|\mathcal{M}_{1}|-\rank(\M_1)=2 . Indexing the operators of \mathcal{M}_{1} in the same order as in Eq. ( 4.4 ), the two top left loops in the first row of Fig. 6 .b correspond to the two vectors \boldsymbol{\ell}_{a}=(1,1,2,0,0) and \boldsymbol{\ell}_{b}=(0,0,1,2,2) in \mathcal{U} reduced to the |\mathcal{M}_{1}|=5 elements of \mathcal{M}_{1} (i.e., the j -th entry of \boldsymbol{\ell} corresponds to the coefficient in front of the j -th operator of \mathcal{M}_{1} in the definition of \mathcal{L}_{q}^{cc} in Eq. ( 68 )). All the other loops of \mathcal{M}_{1} can be obtained by linear combinations of these two loops, which are identified by the two-dimensional vectors in (\mathbb{Z}/q\mathbb{Z})^{\lambda_{1}} shown below each loop diagram in the figure. For example, in the first row, the third loop corresponds to \boldsymbol{\ell}=\boldsymbol{\ell}_{a}+\boldsymbol{\ell}_{b}=(1,1,0,2,2) and the fourth to \boldsymbol{\ell}=\boldsymbol{\ell}_{a}+2\boldsymbol{\ell}_{b}=(1,1,1,1,1) . In summary, the algebraic representation of q -state spin models in terms of linear maps not only makes it easier to manipulate spin models (via vector-matrix operations), it also allows for a better characterization of their properties. We saw in Sec. 3 that the loop expansion of the partition function Z_{\mathcal{M}} of spin models makes a connection between the statistical properties of a model (captured by Z_{\mathcal{M}} ) and its algebraic properties corresponding to linear dependencies between its operators (captured by the loop structure). The framework introduced here formalizes the latter as the kernel of the linear map representing the model, thus providing a formal algebraic characterization of the statistical properties of q -state spin models. 4.6 Equivalence classes of spin models, and their statistical and algebraic properties In the binary case ( q=2 ), Ref. 9 introduces the notion of equivalence classes of spin models, as classes of models related by GTs. They found that these models have the same partition function and thus define the same statistical structure, only observed in different bases. In other words, models of the same class can be seen as different representations of the same abstract statistical model. In particular, they share common statistical and algebraic properties: they have the same loop structure, partition function, and model information-theoretic complexity. Ref. 9 calls these classes “complexity classes”. Let us discuss these results in the more general context of q -state spin models with q\geq 2 . Consider a real-valued q -state spin model \mathcal{M} . A gauge transformation \mathcal{T}_{\boldsymbol{b}} of \mathcal{M} is a bijection of the state space that rearranges the energy landscape of the model, assigning the energy of each state \boldsymbol{s} in \mathcal{M} to another (unique) state \boldsymbol{s}^{\prime}=\boldsymbol{b}(\boldsymbol{s}) in the transformed model \mathcal{M}^{\prime}=\mathcal{T}_{\boldsymbol{b}}[\mathcal{M}] , as described in Definition 19 . As a result, the probability 25 25 25 We recall that for real-valued spin models, the probability to observe a state \boldsymbol{s} is proportional to exponential minus the energy H(\boldsymbol{s}) of the state: p(\boldsymbol{s})\propto\exp(-H(\spin)) . of finding the system in the state \boldsymbol{s} in the model \mathcal{M} is equal to the probability of finding the system in the transformed state \boldsymbol{s}^{\prime}=\boldsymbol{b}(\boldsymbol{s}) in the transformed model \mathcal{M}^{\prime}=\mathcal{T}_{\boldsymbol{b}}[\mathcal{M}] : \displaystyle p(\boldsymbol{s}\,|\,\mathcal{M},\boldsymbol{g})=p(\boldsymbol{s}^{\prime}\,|\,\mathcal{M}^{\prime},\boldsymbol{g}^{\prime})\,. (108) Here, the vector of parameters \boldsymbol{g}^{\prime}=\mathcal{T}_{\boldsymbol{b}}[\boldsymbol{g}] is a permutation of the parameters \boldsymbol{g} of \mathcal{M} such that each transformed operator \phi^{\boldsymbol{\mu}^{\prime}}=\mathcal{T}_{\boldsymbol{b}}[\phi^{\boldsymbol{\mu}}] in \mathcal{M}^{\prime} is parameterized by the same parameter as the operator \phi^{\boldsymbol{\mu}} in \mathcal{M} (see definition 19 ). In equation ( 108 ), the reassignment in state space created by the GT shuffles the state probabilities in the model, but preserves the overall shape of the distribution. In other words, Eq. ( 108 ) expresses that the probability distributions of model \mathcal{M} and of its gauge transformation \mathcal{M}^{\prime} are the same up to permutation of the states. More precisely, one can verify that the transformed spin model \mathcal{M}^{\prime} has the same statistical properties as the original model \mathcal{M} by comparing their partition functions. The partition function ( 3 ) of a spin model is obtained by summing, over all possible states \boldsymbol{s} of the spin system, a term that depends only on the energy of the state (exponential of minus the energy of the state). This sum thus remains unchanged under the one-to-one state reordering of the energy landscape created by a GT (see proof in App. C.2 , which is also valid for spin models with complex-valued Hamiltonian and partition function). In other words, just like in the binary case 9 , q -state spin models related by GTs have the same partition function. Because the partition function encapsulates all the statistical properties of a spin model, this means that models related by GTs describe the same statistical structure, only represented in different bases. From a statistical modeling perspective, the Fisher information matrix (when it is defined) is in general the mathematical object that captures all the statistical properties of a parametric statistical model (not just models that have a partition function, such as spin models). In particular, in the context of information geometry, it can be used as a metric for the model manifold to study the statistical properties of the model 42 ; 3 . For spin models, the Fisher information matrix is given by the Hessian of the log-partition function: \displaystyle[\,\mathcal{I}_{\mathcal{M}}(\boldsymbol{g})\,]_{\boldsymbol{\mu},\boldsymbol{\nu}}=-\left\langle\partial_{g_{\boldsymbol{\mu}}}\partial_{g_{\boldsymbol{\nu}}}\log p(\boldsymbol{s}\,|\,\mathcal{M},\,\boldsymbol{g})\right\rangle_{p(\boldsymbol{s}|\boldsymbol{g},\mathcal{M})}=\partial_{g_{\boldsymbol{\mu}}}\partial_{g_{\boldsymbol{\nu}}}\log Z_{\mathcal{M}}(\boldsymbol{g})\,, (109) and is therefore identical for models related by GTs (assuming the parameters are labeled consistently between the models, as explained for Eq. ( 108 )). This means that spin models related by GTs correspond to the same statistical manifold (up to permutation of the parameters). Therefore, also from this geometrical perspective, models related by GTs are just different representations of the same abstract statistical model. Property 27 . Statistical properties of spin models invariant under GTs. q -state spin models related by gauge transformations have the same partition function (for a model \mathcal{M} and GT \mathcal{T} , Z_{\mathcal{M}}(\boldsymbol{g})=Z_{\mathcal{T}[\mathcal{M}]}(\boldsymbol{g}) ). For real-valued spin models, which can be used as probabilistic models in the context of statistical inference, this implies that they have the same Fisher information matrix. In other words, they describe the same statistical structure represented in different spin bases. More generally, the invariance of the partition function under gauge transformations is valid for all q -state spin models (not just real-valued models). This is straightforward to see using the loop expansion of the partition function in Sec. 3 and the linear algebra framework introduced previously, in which a spin model \mathcal{M} is associated to a linear map f_{\mathcal{M}} . Based on the loop expansion ( 57 ), the partition of a spin model is fully specified by its number of operators (each parameterized by a different parameter) and its loop structure. The number of operators of a model is invariant under GT (by definition 19 ), while the loop structure has been identified as the kernel of the linear map, \mathcal{L}_{q}(\mathcal{M})=\ker(f_{\mathcal{M}}) . Because a GT is an automorphism of the co-domain of f_{\mathcal{M}} (change of basis of the space of state variables – see Fig. 7 ), it has no effect on the kernel of f_{\mathcal{M}} . This can be written down explicitly using the matrix representations \boldsymbol{M} of f_{\mathcal{M}} (and of the model \mathcal{M} ) and \boldsymbol{T} of a given GT (which is an n\times n invertible matrix in (\mathbb{Z}/q\mathbb{Z}) ). The transformed model is represented by the matrix \boldsymbol{M}^{\prime}=\boldsymbol{T}^{-1}\boldsymbol{M} and its loop structure is given by: \displaystyle\mathcal{L}_{q}(\mathcal{M}^{\prime})=\Big\{\boldsymbol{\ell}\in(\mathbb{Z}/q\mathbb{Z})^{K}\;\Big|\;\boldsymbol{T}^{-1}\boldsymbol{M}\,\boldsymbol{\ell}=\boldsymbol{0}\Big\}=\Big\{\boldsymbol{\ell}\in(\mathbb{Z}/q\mathbb{Z})^{K}\;\Big|\;\boldsymbol{M}\,\boldsymbol{\ell}=\boldsymbol{T}\,\boldsymbol{0}\Big\}=\mathcal{L}_{q}(\mathcal{M})\;, where we multiplied by the matrix \boldsymbol{T} on both sides of the equation defining the set. In other words, a spin model and its gauge transformation have the same loop structure, and therefore we recover that they have the same partition function. In doing so, we also identify an algebraic property of spin models that is invariant under GT, namely their loop structure. Moreover, the rank and the dimension of a spin model, which are respectively the cardinality of the maximal set of independent operators within the model, and the cardinality of the minimal independent set of operators that can generate all the operators of the model, are also invariant under GT. Property 28 . Algebraic properties of spin models invariant under GTs. The number of operators, the rank, the dimension, and the loop structure \mathcal{L}_{q} of a q -state spin model are invariant under gauge transformations. For any q -state spin model \mathcal{M} and gauge transformation \mathcal{T} , |\mathcal{T}[\mathcal{M}]|=|\mathcal{M}| , \rank(\T[\M])=\rank(\M) , and \mathcal{L}_{q}(\mathcal{T}[\mathcal{M}])=\mathcal{L}_{q}(\mathcal{M}) . For example, take the top left loop of model \mathcal{M} in Fig. 6 .b; this loop corresponds to the vector \boldsymbol{\ell}=\boldsymbol{u}_{1}+\boldsymbol{u}_{3}+2\boldsymbol{u}_{5} , whose image by f_{\mathcal{M}} is: \displaystyle f_{\mathcal{M}}(\boldsymbol{u}_{1}+\boldsymbol{u}_{3}+2\boldsymbol{u}_{5}) \displaystyle=\boldsymbol{\mu}_{1}+\boldsymbol{\mu}_{3}+2\boldsymbol{\mu}_{5}=\boldsymbol{v}_{1}+\boldsymbol{v}_{2}+2(\boldsymbol{v}_{1}+\boldsymbol{v}_{2})=\boldsymbol{0}\,, (110) where the sums on the right-hand side are taken in (\mathbb{Z}/3\mathbb{Z})^{n} . For the transformed model \mathcal{M}^{\prime}=\mathcal{T}[\mathcal{M}] , the image of the same vector \boldsymbol{\ell} by the linear map f_{\mathcal{M}^{\prime}} associated with \mathcal{M}^{\prime} is also the null vector: \displaystyle f_{\mathcal{M}^{\prime}}(\boldsymbol{u}_{1}+\boldsymbol{u}_{3}+2\boldsymbol{u}_{5}) \displaystyle=\boldsymbol{\mu}_{1}^{\prime}+\boldsymbol{\mu}_{3}^{\prime}+2\boldsymbol{\mu}_{5}^{\prime}=(\boldsymbol{v}_{2}^{\prime}+\boldsymbol{v}_{3}^{\prime})+(\boldsymbol{v}_{1}^{\prime}+2\boldsymbol{v}_{2}^{\prime}+2\boldsymbol{v}_{3}^{\prime})+2\boldsymbol{v}_{1}^{\prime}=\boldsymbol{0}\,, (111) where the vectors \boldsymbol{\mu}_{i}^{\prime}=\mathcal{T}[\boldsymbol{\mu}_{i}] are given in Eq. ( 4.4 ). The representation of the operators has changed from \boldsymbol{\mu}_{j} to \boldsymbol{\mu}_{j}^{\prime} , but not the dependence relations between them. In particular, \boldsymbol{\ell} , which was a loop of \mathcal{M} , remains a loop of \mathcal{M}^{\prime} . Like in the binary case 9 , GTs define an equivalence relation between q -state spin models (one can easily check for reflexivity, symmetry, transitivity 26 26 26 Reflexivity: a spin model is a GT of itself, where the GT is the identity. Symmetry: consider a model \mathcal{M}^{\prime} obtained by the GT \mathcal{T} of another model \mathcal{M} , then \mathcal{M} is also the gauge transformation of \mathcal{M}^{\prime} using \mathcal{T}^{-1} . Transitivity: consider two GTs \mathcal{T}_{1} and \mathcal{T}_{2} , and the transformed model \mathcal{M}^{\prime}=\mathcal{T}_{1}[\mathcal{M}] and \mathcal{M}^{\prime\prime}=\mathcal{T}_{2}[\mathcal{M}^{\prime}] , then \mathcal{M}^{\prime\prime}=\mathcal{T}[\mathcal{M}] where \mathcal{T}=\mathcal{T}_{2}[\mathcal{T}_{1}] is also a GT resulting from the composition of \mathcal{T}_{1} and \mathcal{T}_{2} . ). This equivalence relation divides the (superexponential) space of the 2^{q^{n}-1} spin models into equivalence classes of models that share common statistical and algebraic properties. In section 5 , we will focus on the subset of classes corresponding to minimally complex models 15 . Property 29 . Equivalence classes of q -state spin models and their properties. Gauge transformations define an equivalence relation between q -state spin models, dividing the space of models into equivalence classes. Models of the same class are different representations of the same abstract statistical model. Each class is thus characterized by the statistical and algebraic invariants given in Property 27 and 28 . 4.7 Discussion: equivariant modeling and learning symmetries of data under gauge transformations The gauge transformation of a discrete dataset simply re-writes the data in a different basis, without any loss or added information or noise. Ideally, a perfect model selection procedure would be able to find models that are consistent for the original data and its transformed version, as illustrated in Figure 1 in the introduction. In other words, this ideal model selection would be equivariant under GTs. Such approach is theoretically possible if we select among all q -state spin models, because this family of models is invariant under GTs (for any given q ). However, brute force selection of the best model among all is impossible in practice, due to the huge set of models (super-exponential in the number of spins). In Section 5 , we extend to discrete data the work of Ref. 15 on minimally complex models, which are a sub-family of spin models within which one can perform equivariant model selection in practice. More generally, if one wants to tackle model selection among all q -state spin models, it is important to find principled ways to reduce the number of parameters and the set of possible models for a given dataset. One approach is to focus on modeling symmetries of the data, instead of specific correlation patterns. If a dataset is invariant (up to noise) under certain bijective transformations, then a good model should encode that invariance, i.e., it should be invariant under the same transformation. This reduces the set of candidate models. In other words, we simplify the problem of identifying relevant correlation patterns of the data by searching first for relevant symmetries of the data. Indeed, it is in general difficult to identify in a robust manner the set of the most relevant (high-order) correlation patterns of a dataset, because these patterns are typically not independent from each other and, as a result, many combinations of possible relevant patterns can explain the data similarly 27 27 27 This problem is in fact equivalent to identifying the best spin model for the data, by definition of maximum entropy models 25 . . In contrast, one can treat symmetries of the data independently from each other, and each newly uncovered symmetry further reduces the pool of possible candidate models. In the following, we formalize this idea based on the notion of invariance under GTs. As discussed in Sec. 4.2 , applying a GT to a dataset permutes the probability of occurrence of the states in the empirical distribution. However, certain GTs can leave the empirical distribution fully invariant, by only permuting states that have the same probability. Such invariance can be interpreted as a symmetry of the data under GT. The definition of GTs thus allows us to formalize the notion of generalized symmetries in discrete data, as the invariance of the empirical probability distribution under GT. These symmetries go beyond ordinary symmetries, such as translational and reflection symmetries for spatially organized variables, or symmetries under permutations of spin variables. Definition 24 . Generalized symmetry of (stationary) discrete data. We call symmetry of a discrete dataset the invariance of its empirical distribution under a gauge transformation. For q -state spin models, gauge transformations are changes of representation of the models. They transform a model’s architecture (i.e., which operators are in the model), while preserving its statistical and algebraic properties (e.g., partition function and loop structure). However, certain GTs can leave a given model architecture fully invariant, by transforming each operator of the model into a spin operator that is already in the model. In other words, a model \mathcal{M} and its transformation \mathcal{T}[\mathcal{M}] have the same set of operators and thus correspond to the same parametric model. For example, take Bob’s model in the introduction Figure 1 . The permutation of the spins s_{1} and s_{2} is a GT that leaves the model’s architecture invariant. Equivalently, for Alice’s model, the GT (\sigma_{1}^{\prime},\sigma_{2}^{\prime},\sigma_{3}^{\prime})=(\sigma_{1},\,\sigma_{1}\sigma_{2}\sigma_{3},\,\sigma_{3}) leaves the model invariant (as it permutes the field operator \sigma_{2} with the three-body operator \sigma_{1}\sigma_{2}\sigma_{3} ). We call such invariance of the model architecture under GT a symmetry of the spin model. Contrary to the definition 24 of symmetry of data, the symmetry of a model under GT doesn’t necessarily leave the model probability distribution invariant, because the parameters associated with the permuted operators are then also permuted. For the model probability distribution to remain invariant for any value of the parameters, the parameters of the permuted operators must be equal (degenerate parameters). Definition 25 . Generalized symmetry of q -state spin models. We call symmetry of a spin model the invariance of its architecture (which operators are in the model) under a gauge transformation. We call “strong” symmetry of a spin model the invariance of the model probability distribution under a GT. Such invariance requires both an invariance of the model architecture and the degeneracy of the model parameters associated with the operators permuted by the GT. We can thus exploit generalized symmetries of a discrete dataset to reduce the pool of candidate spin models to those that have the same symmetries. An invariance of the data under a GT should be reflected in the candidate models as a strong symmetry, which imposes a degeneracy of the parameters associated with the operators permuted by the GT 28 28 28 For example, take a binary dataset with 3 spins that is invariant under the GT characterized by the inverse transformation \boldsymbol{T}^{-1}=\begin{pmatrix}1&0&0\\ 1&1&0\\ 0&1&1\end{pmatrix} . Then the operators (100),(110),(101),(111) should be given the same parameters as well as the operators (011) and (010) for the model to be strongly symmetric under the same transformation (this can be checked by multiplying the matrix \boldsymbol{T}^{-1} with each of these operators as in Eq. ( 96 )). : they must either all be absent from the model or all have the same parameter. The model selection procedure should then decide if this degenerate parameter is relevant or if these operators should be all be removed from the model 29 29 29 Note that a symmetry under GT will not reduce the set of models to a specific subset of equivalence classes, but instead it will invalidate candidate models from all classes. A symmetry under a given GT is indeed representation-dependent. For each transformation under which a model \boldsymbol{M} is invariant, there is a corresponding transformation under which another model of the same class is invariant. Consider a transformation \boldsymbol{T}_{1} under which \boldsymbol{M}_{1} is invariant: \boldsymbol{T}_{1}\boldsymbol{M}_{1}=\boldsymbol{M}_{1} . Consider another model \boldsymbol{M}_{2} of the same class: there exists a GT \boldsymbol{T} such that \boldsymbol{M}_{2}=\boldsymbol{T}\boldsymbol{M}_{1} . The model \boldsymbol{M}_{2} is then invariant under the GT \boldsymbol{T}_{2}=\boldsymbol{T}\boldsymbol{T}_{1}\boldsymbol{T}^{-1} , as it satisfies that \boldsymbol{T}_{2}\boldsymbol{M}_{2}=\boldsymbol{M}_{2} . Furthermore, if \boldsymbol{T} and \boldsymbol{T}_{1} commute, then \boldsymbol{T}_{2}=\boldsymbol{T}_{1} , which means that the models \boldsymbol{M}_{1} and \boldsymbol{M}_{2} are invariant under the same GT \boldsymbol{T}_{1} . . For real data, the probabilities of occurrence of the states are known up to some uncertainty that depends on the size of the data: the larger the number of datapoints, the smaller the uncertainty. To find all the symmetries of a finite dataset, one should take into account the level of uncertainty (even more so in undersampling regimes). This can be done by reducing the noise in the empirical probability distribution, for instance, by assigning the same probability to states that have similar frequencies at the level of precision warranted by the data (e.g., following the procedure of 22 ). A smaller number of different relevant probabilities in the empirical distribution increases the number of symmetries observed in the data, and therefore reduces the number of parameters in the model. This is a consequence of the duality between mixture models and models of the exponential family 2 , which was exploited for instance for model reduction and parameter fitting for small systems in 19 . Such a procedure can significantly reduce the number of possible model parameters. A model selection procedure would then have fewer parameters to select from to identify if they are relevant or not. These parameters would also be associated with larger “macro”-patterns (composed of multiple operators). Such an approach has the potential to greatly simplify the model selection procedure and lead to more robust model discovery. 5 Limiting the search to Minimally Complex Models (MCMs) Despite the existence of equivalent models, the space of models is still extremely large, making it difficult to perform model selection. Ref. 15 proposes to perform model selection among a sub-family of spin models that they call Minimally Complex Models (MCMs), for which all the quantities of interest in the context of statistical inference are computationally cheap to calculate, making model selection feasible in practice among these models. In particular, Ref. 15 introduced MCMs as an alternative to pairwise models that respects the structure of gauge transformations (GTs), because the family of MCMs is invariant under GT (the GT of an MCM is also an MCM). This is not the case for families of spin models restricted to have interactions only up to a certain order, such as pairwise models. Working with MCMs thus brings a new perspective to statistical modeling, by making it possible to tackle data modeling problems in a way that is independent of the basis in which the data was originally represented. This is interesting especially for systems where it is not clear if the current representation of the data is the most meaningful, or when one is interested in tackling a modeling problem from the most general perspective, in the absence of any information about the system. Model selection with MCMs is also efficient thanks to the peculiar interaction structure of MCMs, in which interactions are grouped into independent sub-systems. More precisely, in some representations, an MCM corresponds to a factorization of the model multivariate probability distribution over subsets of basis variables; i.e., the model assumes that these subsets are statistically independent from each other (see Fig. 8 ). Performing model selection among MCMs thus aims to uncover the factorization of the model probability distribution that best matches the structure of the data. Such factorization reduces the dimensionality of the statistical inference problem, while preserving most of the relevant information within the data. MCMs can thus be used to identify groups of variables that carry most of the multivariate information in the data, or to facilitate the modeling problem for large systems by breaking it down into lower-dimensional ones. Ref. 1 likens this approach to performing community detection for data (by analogy to community detection in network analysis), giving a simple interpretation to MCMs in terms of community structure. In this section, we focus on a subset of q -state spin models that generalize the framework of minimally complex models 15 to discrete systems. Figure 8: (colors online) Visualization of MCMs as factorization in state space. Left. In each row, the left panel shows an MCM based on four discrete variables (\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4}) with two ICCs represented in different colors. The MCM is represented in a preferred basis, which means that each ICC contains all possible operators over the shown subset of \alpha -variables. The value of q for the discrete variables is not yet specified and the diagrams can be read for any chosen value of q . For example, for the top row: for q=2 , the red ICC has the q^{2}-1=3 operators (\mu_{1},\mu_{2})\in\{(1,0),(0,1),(1,1)\} ; for q=3 , the red ICC has the q^{2}-1=8 operators (\mu_{1},\mu_{2})\in\{(1,0),(2,0),(0,1),(0,2),(1,1),(2,2),(1,2),(2,1)\} . Right. The panel represents the factorization in state space (for q=2 and q=3 ) that results from the MCM partition of the basis variables \alpha_{i} shown in the left panel. The model probability distribution can be written as the product of joint distributions over lower dimensional subspaces shown in colors (line, surface, or volume). The color (green or red) refers to the corresponding ICC in the left panel and each marker represents a state of the system reduced to these subspaces (e.g., for the top panel and q=2 , the pair of variables (\alpha_{1},\alpha_{2}) can take the values \{(0,0),(1,0),(0,1),(1,1)\} , hence the four markers in the red area). The probability of the states that are not represented by a colored marker is obtained by products of the probabilities of the sub-states that are represented by a marker. When written in a preferred basis, the factorization of the state space resulting from the same MCM partition of the basis variables into ICC (as in the left panel) doesn’t depend on the value of the discretization q of the variables. The only difference is the increase of the number of states in each subspace with q . 5.1 Definitions Minimally complex models (MCMs) are defined in the context of binary data as models constructed from the union of independent complete components (ICCs) 15 . Here, we generalize to the discrete case the definitions of complete components (CCs), independent components (ICs), and MCMs. We call a “component” of a spin model \mathcal{M} any subset of operators of \mathcal{M} . For q prime, we can directly extend to q>2 the definition of complete components from Ref. 15 . Definition 26 . Complete Component (CC), for q prime. A complete component is a set of operators \mathcal{M}_{a}\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*} that verifies that, for any two operators (\boldsymbol{\mu},\boldsymbol{\nu})\in\mathcal{M}_{a}^{\,2} , all the operators obtained by linear combinations of \boldsymbol{\mu} and \boldsymbol{\nu} in (\mathbb{Z}/q\mathbb{Z})^{n} are in \mathcal{M}_{a}\cup\boldsymbol{0} , i.e.: \displaystyle\forall(\boldsymbol{\mu},\boldsymbol{\nu})\in\mathcal{M}_{a}^{2}\,,\qquad\forall(c,d)\in(\mathbb{Z}/q\mathbb{Z})^{2},\qquad c\,\boldsymbol{\mu}+d\,\boldsymbol{\nu}\in\mathcal{M}_{a}\cup\boldsymbol{0}\,. (112) In other words, \mathcal{M}_{a}\cup\boldsymbol{0} is a vector subspace of (\mathbb{Z}/q\mathbb{Z})^{n} of dimension r_{a} , where r_{a} is the cardinality of the largest linearly independent set in \mathcal{M}_{a} (namely the rank of \mathcal{M}_{a} – see Definition 14 ). In this definition, the set \mathcal{M}_{a} of operators can be a subset of operators of a model (hence the use of the term “component” instead of “model”). We recall that the interaction vector c\,\boldsymbol{\mu}+d\,\boldsymbol{\nu} is associated with the spin operator \phi^{c\,\boldsymbol{\mu}+d\,\boldsymbol{\nu}}(\boldsymbol{\alpha})\doteq[\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})]^{c}\,[\phi^{\boldsymbol{\nu}}(\boldsymbol{\alpha})]^{d} . For q>2 , because of conjugate operators, the vector c\,\boldsymbol{\mu}+d\,\boldsymbol{\nu} can be equal to \boldsymbol{0} even for (c,d)\neq(0,0) , which is why we added the element \boldsymbol{0} to \mathcal{M}_{a} in Eq. ( 112 ). This doesn’t happen in the binary case 15 . Extending Definition 26 to non-prime values of q would define as being “complete” model components that we don’t want to consider complete in the context of MCMs. For example, take the component \mathcal{M}_{a}=\{(2,2)\} with a single pairwise interaction for n=2 spins and q=4 . This component satisfies Eq. ( 112 ), because the only multiples of the operator (2,2) in (\mathbb{Z}/4\mathbb{Z})^{2} are (0,0) and itself, which are both in \mathcal{M}_{a}\cup\boldsymbol{0} . The component \mathcal{M}_{a} is in some sense complete, but it is isomorphic to \mathbb{Z}/2\mathbb{Z} and not to \mathbb{Z}/q\mathbb{Z} (here q=4 ). Considering such component as complete is problematic, because an MCM would then correspond to a factorization over “CC” defined for variables of different types (i.e., with different values of q ). We would also lose the re-parametrization property of CC (see Property 40 below), which is necessary for the efficient computation of many quantities of interest for modeling data with MCMs (see Sec. 5.4 ). To exclude this possibility, we give the following general definition of complete components, valid for any integer value of q . Definition 27 . (for all q )  Complete Component (CC). A set of operators is said to be complete if it is equal to the set of all the operators generated by an independent set of operators (see Definition 11 of independent operators). Formally, consider a set of operators \mathcal{M}_{a}\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*} and let I=\{\boldsymbol{\mu}_{1},\dots,\boldsymbol{\mu}_{r_{a}}\} be a maximal independent set of operators in \mathcal{M}_{a} . The model component \mathcal{M}_{a} is said complete if its elements are all the operators generated by I , \displaystyle\mathcal{M}_{a}=\langle I\rangle_{gen}^{*}=\bigg\{\,\sum_{j=1}^{r_{a}}c_{j}\,\boldsymbol{\mu}_{j}\;\Big|\;\,(c_{1},\dots,c_{r_{a}})\in[(\mathbb{Z}/q\mathbb{Z})^{r_{a}}]^{*}\bigg\}\,, (113) where we used the notation * to indicate that we exclude the null vector (which doesn’t correspond to an operator). In other words, \mathcal{M}_{a}\cup\boldsymbol{0} is a submodule of (\mathbb{Z}/q\mathbb{Z})^{n} isomorphic to (\mathbb{Z}/q\mathbb{Z})^{r_{a}} , where r_{a} is the cardinality of I (namely, the rank of \mathcal{M}_{a} , denoted \rank(\M_a) ). From this definition, it follows that the number of operators in a complete component of rank r_{a} is equal to the number of nonzero vectors in (\mathbb{Z}/q\mathbb{Z})^{r_{a}} , which is q^{r_{a}}-1 . Property 30 . Number of operators in a CC. The number of operators in a complete component \mathcal{M}_{a} is |\mathcal{M}_{a}|=q^{r_{a}}-1 , where r_{a} denotes the rank of \mathcal{M}_{a} . We can then directly extend the definition of independence between complete components from the binary case to the more general discrete case. Definition 28 . Independence between CC and Minimally Complex Models (MCMs). A set of complete components \{\mathcal{M}_{a}\}_{a\in\mathcal{A}} is said to be independent if none of the operators of a given component \mathcal{M}_{a} can be obtained by linear combinations of operators of the other components (i.e., generated by the set of operators \cup_{a^{\prime}\in\mathcal{A}\backslash a}\mathcal{M}_{a^{\prime}} ). This then leads to the definition of Minimally Complex Models (MCMs) as models formed by the union of independent complete components (ICCs), \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} . In the following, we give a more general definition of independence between components, for components that are not necessarily complete. Our goal is to build a general formalism that can be used for any q -state spin model (not just MCMs) and which allows for modeling data in a basis independent way. For general spin models, the notion of independence between components is directly linked to a factorization property of the model probability distribution (see Property 39 below); this factorization can be in the original representation of the data or in another gauge-transformed basis. In this framework, MCMs are a natural stepping stone towards modeling the data with more complex spin models. To construct this formalism, we first introduce the definition of basis of a component , which we will then use to define independent components. Definition 29 . Basis and dimension of a component. A basis of a component \mathcal{M}_{a} , denoted B_{\mathcal{M}_{a}} , is a minimal set of d_{a} independent operators 30 30 30 The operators of a basis of a component \mathcal{M} are not necessarily in \mathcal{M} . that can generate all the operators of \mathcal{M}_{a} : \displaystyle\boldsymbol{B}_{\mathcal{M}_{a}}=(\boldsymbol{\mu}_{1},\cdots,\boldsymbol{\mu}_{d_{a}})\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*}\;\;\textrm{such that}\;\mathcal{M}_{a}\subseteq\langle\boldsymbol{B}_{\mathcal{M}_{a}}\rangle_{gen}\;. (114) We call the cardinality d_{a} of such basis the dimension of the component and denote it \dim(\mathcal{M}_{a}) . By definition, in an n -spin system, \dim(\mathcal{M}_{a})\leq n for any model component \mathcal{M}_{a} . In the following, we consider the operators of the basis to be ordered, which we indicated in Eq. ( 114 ) by using parentheses instead of curly brackets in (\boldsymbol{\mu}_{1},\cdots,\boldsymbol{\mu}_{d_{a}}) and a bold symbol for \boldsymbol{B}_{\mathcal{M}_{a}} . This definition is also valid if the component coincides with the whole model, thus defining the basis and the dimension of a q -state spin model. The basis of a component is not necessarily unique, but its dimension is (by definition). Note the difference between the rank and the dimension of a component: the rank of a component is the cardinality of the largest independent set within the component, whereas its dimension is the cardinality of the smallest independent set containing the component. If q is prime, the dimension and the rank of a component are always equal, but this is not necessarily the case if q is not prime, for which the dimension can be larger than the rank 31 31 31 For example, consider a two-spin system with q=4 and the model \mathcal{M}=\{(2,0)\} . This model has a dimension \dim(\mathcal{M})=1 because it can be generated by the single independent operator (1,0) (and not less), but it’s rank is \rank(\M)=0 because \boldsymbol{\mu}=(2,0) is not an independent operator over (\mathbb{Z}/4\mathbb{Z})^{2} (as 2\boldsymbol{\mu}=\boldsymbol{0} ). . However for CC, any maximal independent set of operators in the component can generate the whole component, by definition 27 of completeness. This means that such a set is also a basis of the CC and therefore that the dimension of a CC is equal to its rank for all values of q . In general, q -state spin models are difficult to work with if q is not prime, due to (\mathbb{Z}/q\mathbb{Z}) not being a field, but thanks to this last property (or more generally, to the completeness of the components), this is not an issue for MCMs. Property 31 . Basis, dimension, and rank of a CC. Any maximal independent set of operators in a CC is also a basis of the component. Consequently, the dimension and the rank of a CC are equal, for all integer values of q (prime or not). In the following, we will denote by r_{a}=\rank(\M_a)=\dim(\mathcal{M}_{a}) both the rank and the dimension of a CC \mathcal{M}_{a} . We have already introduced a definition of spin basis in Sec. 4 , in the context of the definition 17 of gauge transformations (GTs). We defined a spin basis for an n -spin system as an ordered set of n independent operators, denoted \boldsymbol{b}=(\phi^{\boldsymbol{\mu}_{1}},\cdots,\phi^{\boldsymbol{\mu}_{n}}) , and a GT as a change of spin basis of the form \mathcal{T}:\boldsymbol{s}\to\boldsymbol{s}^{\prime}=\boldsymbol{b}(\boldsymbol{s}) . A basis of a component in Definition 29 also corresponds to a spin basis, but it is reduced to the (minimal) subspace in which the component is defined. Note that, in Definition 29 and throughout the paper, we used the term “operator” for both the spin operator \phi^{\boldsymbol{\mu}} (proper use of the term) and its vector representation \boldsymbol{\mu} . For clarity and coherence of the notations, we will denote a basis of a component \mathcal{M}_{a} by \boldsymbol{b}_{\mathcal{M}_{a}}=(\phi^{\boldsymbol{\mu}_{1}},\cdots,\phi^{\boldsymbol{\mu}_{d_{a}}}) when written in terms of the spin operators \phi^{\boldsymbol{\mu}} and by \boldsymbol{B}_{\mathcal{M}_{a}}=(\boldsymbol{\mu}_{1},\cdots,\boldsymbol{\mu}_{d_{a}}) when written in terms of their vector representation \boldsymbol{\mu} . Using the definition of basis of a component, we now define independent components. Definition 30 . Independent Components (ICs). Consider a set of operators \mathcal{M}\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*} formed by the union of disjoint components \mathcal{M}_{a} : \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} , where \mathcal{A} is a set of labels identifying the components. Consider a basis \boldsymbol{B}_{\mathcal{M}_{a}} for each component \mathcal{M}_{a} . The set of components \{\mathcal{M}_{a}\}_{a\in\mathcal{A}} is said to be independent if, for each component \mathcal{M}_{a} , none of the operators generated by \boldsymbol{B}_{\mathcal{M}_{a}} can be generated by the combined bases of the other components (except for the null vector): \displaystyle\forall\boldsymbol{\mu}\in\langle\boldsymbol{B}_{\mathcal{M}_{a}}\rangle_{gen}^{*}\,,\qquad\boldsymbol{\mu}\notin\bigg\langle\displaystyle\bigcup_{\begin{subarray}{c}a^{\prime}\in\mathcal{A}\\ a^{\prime}\neq a\end{subarray}}\boldsymbol{B}_{\mathcal{M}_{a^{\prime}}}\bigg\rangle_{gen}\;, (115) where \langle S\rangle_{gen} denotes the set of all the operators generated by a set S of operators over (\mathbb{Z}/q\mathbb{Z})^{n} . In other words, the bases \boldsymbol{B}_{\mathcal{M}_{a}} for all a\in\mathcal{A} generate independent subspaces of (\mathbb{Z}/q\mathbb{Z})^{n} (each isomorphic to (\mathbb{Z}/q\mathbb{Z})^{d_{a}} , where d_{a}=\dim(\mathcal{M}_{a}) ), and the operators of each component \mathcal{M}_{a} belong only to the subspace defined by \boldsymbol{B}_{\mathcal{M}_{a}} . For example, any choice of decomposition of an independent model (see Definition 16 ) into components gives a set of independent components. As a direct consequence of the independence between the components \mathcal{M}_{a,\,a\in\mathcal{A}} , one can construct a basis \boldsymbol{B}_{\mathcal{M}} of a model \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} by combining the elements of the basis \boldsymbol{B}_{\mathcal{M}_{a}} of each component. The resulting set of operators, \boldsymbol{B}_{\mathcal{M}}=\cup_{a\in\mathcal{A}}\boldsymbol{B}_{\mathcal{M}_{a}} , is indeed still independent, thanks to Eq. ( 115 ). This is generally not the case for random choices of decomposition of \mathcal{M} in components \mathcal{M}_{a} , as the components can belong to overlapping (minimal) subspaces of (\mathbb{Z}/q\mathbb{Z})^{n} . We recall that a basis was defined as an ordered set; here we assume that the elements in \mathcal{A} have an order, and we create the combined basis \boldsymbol{B}_{\mathcal{M}} by “gluing” together the operators of the basis-component \boldsymbol{B}_{\mathcal{M}_{a}} in that order (same for the notation \boldsymbol{b}_{\mathcal{M}}=\cup_{a\in\mathcal{A}}\boldsymbol{b}_{\mathcal{M}_{a}} that will also be used below). In practice, the specific choice of ordering of these basis components doesn’t matter, but it must be consistent throughout the analysis. Property 32 . Basis and dimension of ICs. Consider a model \mathcal{M} formed by the union of components, \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} , and consider a basis \boldsymbol{B}_{\mathcal{M}_{a}} for each component. If the components \mathcal{M}_{a} are independent, then the set of operators \boldsymbol{B}=\cup_{a\in\mathcal{A}}\boldsymbol{B}_{\mathcal{M}_{a}} forms a basis of \mathcal{M} , and the dimension of \mathcal{M} is thus equal to the sum of the dimensions of the ICs \mathcal{M}_{a} , \dim(\mathcal{M})=\sum_{a\in\mathcal{A}}\dim(\mathcal{M}_{a}) . Finally, we recover the definition 28 of minimally complex models by combining the definitions of complete components and independent components 32 32 32 If all the independent components \mathcal{M}_{a} in Def. 30 are also complete, then, in Eq. ( 115 ), the set \langle\boldsymbol{B}_{\mathcal{M}_{a}}\rangle^{*} of operators generated by a basis \boldsymbol{B}_{\mathcal{M}_{a}} of a component is equal to the component, \langle\boldsymbol{B}_{\mathcal{M}_{a}}\rangle^{*}=\mathcal{M}_{a} (by definition of CC), and Def. 30 becomes Def. 28 of independence between CC. . Definition 31 . Minimally Complex Models (MCMs). A q -state spin model is a minimally complex model if its set of operators, \mathcal{M}\subseteq[(\mathbb{Z}/q\mathbb{Z})^{n}]^{*} , is formed by the union of independent complete components (ICCs) \mathcal{M}_{a} : \displaystyle\mathcal{M}=\bigcup_{a\in\mathcal{A}}\mathcal{M}_{a}\,, (116) where \mathcal{A} is a set of labels identifying the ICCs. In other words, \{\mathcal{M}_{a}\}_{a\in\mathcal{A}} is a set of independent components and, for all a\in\mathcal{A} , the component \mathcal{M}_{a} is complete. Each ICC thus completely models an independent subspace of (\mathbb{Z}/q\mathbb{Z})^{n} . Note that contrary to the binary case, an independent model, as defined in Definition 13 , is not an MCM. This is because each independent subspace of dimension d_{a}=1 requires (q-1) operators to be fully modeled by a q -state spin model, while an independent model only has one operator per dimension (which is strictly less than (q-1) for q>2 ). However, we can define a notion of independent MCM in the discrete case, which reduces to that of independent model in the binary case. Definition 32 . Independent Minimally Complex Models (IMCMs). MCMs for which each ICC has rank 1. These models will be useful for the search algorithms for the best MCM proposed in Sec. 6.1 . Finally, MCMs inherit all the properties of CCs and ICs mentioned above. Property 33 . Number of operators, basis, dimension, and rank of an MCM. Consider an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} with ICCs \{\mathcal{M}_{a}\}_{a\in\mathcal{A}} . As a consequence of the completeness of the components, the dimension and the rank of each component \mathcal{M}_{a} are equal (see Property 31 ), denoted r_{a}=\rank(\M_a)=\dim(\mathcal{M}_{a}) , and the number of operators in \mathcal{M} is given by (see Property 30 ): \displaystyle|\mathcal{M}|=\sum_{a\in\mathcal{A}}(q^{r_{a}}-1)\,. (117) Thanks to the independence between the components \mathcal{M}_{a} , one can obtain a basis of \mathcal{M} by combining the bases B_{\mathcal{M}_{a}} of its components (see Property 32 ): \displaystyle B_{\mathcal{M}}=\cup_{a\in\mathcal{A}}B_{\mathcal{M}_{a}}\,. (118) The dimension of \mathcal{M} is thus equal to the sum of the dimensions of its ICCs \mathcal{M}_{a} , and so is its rank: \rank(\M)=\dim(\mathcal{M})=\sum_{a\in\mathcal{A}}r_{a} . In the following, we will denote by r both the rank and the dimension of an MCM \mathcal{M} . Figure 9 gives four examples of MCMs. Observe that in some representations, the complete components \mathcal{M}_{a} of an MCMs can spread over more than r_{a}=\rank(\M_a) variables. For example, the two models in panel (b) both have a single ICC of rank r_{a}=1 . In the top model, this ICC spreads over two variables (with pairwise operators), whereas in the bottom model, the ICC is compact, based solely on one variable, and we can immediately see that the component is complete and of rank 1. Similarly, the two models in panel (a) both have two ICCs of rank r_{a}=1 and 2 respectively. It is not easy to see that the top model is an MCM, because the ICC of rank 2 is spread over three variables. In contrast in the bottom model, one can clearly identify the two ICCs, with all possible operators based on \sigma_{1} and \sigma_{2} for one ICC, and all the operators based on \sigma_{3} for the other ICC. In these examples, the top and bottom models of each panel are related by gauge transformations, which means that they are different representations of the same abstract MCM (see sec. 4 ). In the following section, we discuss GTs of MCMs. Figure 9: Examples of MCMs and their GTs to a preferred basis. Each box contains an example of an MCM. Operators are represented using the same convention as in Fig. 6 . In panel b), the green color is also used to indicate that a spin is raised to the third power in the corresponding operator (e.g., in model \mathcal{M} , the green pairwise link represents the operator s_{1}^{\,3}s_{2}^{\,3} ). For each example, we use the GT \mathcal{T} to transform the top model into the bottom one, and the inverse GT \mathcal{T}^{-1} to go back to the top model. The bottom model \mathcal{M}^{\prime} is in a preferred basis, in which each ICC appears in a compact complete form over a subset of spins (circled with gray dashed lines). The matrix representations of these models and of their GTs are available in App. D.1 . a) Example of two equivalent MCMs with q=3 for n=3 spins; these models have two ICCs with rank 2 and 1 respectively. For clarity we represented the models using the decomposition \mathcal{M}=\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} , where the operators in \mathcal{M}_{1}^{*} are the c.c. of the operators in \mathcal{M}_{1} . The transformed model is obtained using \mathcal{M}^{\prime}=\mathcal{M}_{1}^{\prime}\cup\mathcal{M}_{1}^{*\prime} , where \mathcal{M}_{1}^{\prime}=\mathcal{T}[\mathcal{M}_{1}] (see Sec. 4.4 ). b) Example of two equivalent MCMs, \mathcal{M} and \mathcal{M}^{\prime} , with q=4 for n=2 spins; these models have a single ICC of rank 1 . 5.2 Gauge transformations of MCMs, equivalence classes, and counting Similarly to the binary case, the family of MCMs for q>2 is invariant under gauge transformations (GTs), meaning that the GT of an MCM is also an MCM (see Def. 17 for the definition of GTs). Indeed, under a GT, a complete component remains complete and with the same rank, and a set of independent components remains independent (see App. D.2 ). This is an interesting property of MCMs if one wants to tackle model selection of discrete data from a more general perspective, independently of the basis in which the data is originally represented. In the following, we lay out the foundations to work with MCMs in a basis-independent way. Property 34 . Gauge transformation of an MCM. The gauge transformation of an MCM is also an MCM and has ICCs of the same ranks as the original model. Figure 9 shows examples of GTs of MCMs. In particular, it highlights the transformation of MCMs into a preferred basis , a useful notion introduced in the binary case 15 . As noted previously, in some representations, a complete component \mathcal{M}_{a} can spread over more than r_{a}=\rank(\M_a) basis variables. For example, the top model for q=4 in Fig. 9 .b has a single CC \mathcal{M}=\{(1,1),(2,2),(3,3)\} with operators of order two despite having only a rank r=1 . Using the GT \sigma_{1}=s_{1}s_{2} and \sigma_{2}=s_{1} , \mathcal{M} is transformed into the model \mathcal{M}^{\prime}=\{(1,0),(2,0),(3,0)\} (see App. D.1 ), in which all the operators are based solely on r=1 variable (see Fig. 9 .b bottom). Ref. 15 introduced the notion of preferred bases of an MCM, which are spin bases in which each ICC \mathcal{M}_{a} of the MCM appears in a compact form, based solely on r_{a}=\rank(\M_a) basis elements just like for \mathcal{M}^{\prime} above. The model in Fig. 9 .a bottom is another example of an MCM represented in a preferred basis. Definition 33 . Preferred basis of an MCM. A preferred basis of an MCM is a spin basis, \boldsymbol{b}^{*}=(\phi^{\boldsymbol{\mu}_{1}},\cdots,\phi^{\boldsymbol{\mu}_{n}}) , in which each ICC \mathcal{M}_{a} is based solely on r_{a} basis elements, where r_{a} is the rank (and dimension) of \mathcal{M}_{a} . In such basis, each ICC appears in a compact form and the MCM corresponds to a partition of a subset of the basis variables in which each part identifies an ICC (see dashed outlines in Fig. 9 bottom – the variables are fully connected within each part, with operators of all orders, and not connected between the parts). In other words, a preferred spin basis \boldsymbol{b}^{*} for an MCM defines a GT \mathcal{T}:\boldsymbol{s}\to\boldsymbol{s}^{\prime}=\boldsymbol{b}^{*}(\boldsymbol{s}) (see Definition 17 ) that transforms the MCM into its compact representation, with each ICC based on a minimal number of basis variables. More generally, one can define a preferred basis for any set of ICs (for which the components are not necessarily complete) as a basis in which each component \mathcal{M}_{a} is only expressed over d_{a}=\dim(\mathcal{M}_{a}) basis variables. It is always possible to construct a preferred basis for an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} (and more generally for a set of ICs), simply by combining the elements of a basis \boldsymbol{b}_{\mathcal{M}_{a}} for each IC \mathcal{M}_{a} , thanks to the independence between the ICCs (see Property 32 ). We obtain a spin basis of the form \boldsymbol{b}^{*}=\cup_{a\in\mathcal{A}}\,\boldsymbol{b}_{\mathcal{M}_{a}}\cup\overline{\boldsymbol{b}_{\mathcal{M}}} , where \overline{\boldsymbol{b}_{\mathcal{M}}} is a set of (n-\dim(\mathcal{M})) independent operators chosen to complete the spin basis. In such a basis, the operators of each component \mathcal{M}_{a} would be based solely on their respective basis variables \boldsymbol{b}_{\mathcal{M}_{a}} (by definition 30 of ICs), which is precisely what we want for a preferred basis. Moreover, for MCMs, because the component \mathcal{M}_{a} are complete, we can choose any set of r_{a}=\rank(\M_a) independent operators in \mathcal{M}_{a} to define its basis \boldsymbol{b}_{\mathcal{M}_{a}}=(\phi^{\boldsymbol{\mu}^{a}_{1}},\cdots,\phi^{\boldsymbol{\mu}^{a}_{r_{a}}}) (see Property 31 ). This is precisely the construction we followed in each panel of Fig. 9 to define the GT \mathcal{T} (from top to bottom) of the model \mathcal{M} into a preferred basis. In panel b), the top model \mathcal{M} has a single CC, which can be fully generated by the operator \boldsymbol{\mu}_{1}=(1,1) . We used this operator to create a preferred basis for \mathcal{M} , by defining the first basis element of the GT \mathcal{T} as \sigma_{1}=\phi^{\boldsymbol{\mu}_{1}}(\boldsymbol{s})=s_{1}s_{2} and choosing the second basis element to be independent from \sigma_{1} . In panel a), the model \mathcal{M} has two ICCs; we constructed a preferred basis by combining the elements of a basis \boldsymbol{b}_{a} for each ICC \mathcal{M}_{a} , for which any choice of r_{a} independent operators in \mathcal{M}_{a} can be used. The operators \boldsymbol{\mu}_{1}=(1,1,0) and \boldsymbol{\mu}_{2}=(1,0,2) defining the first two variables of the preferred basis, \sigma_{1}=\phi^{\boldsymbol{\mu}_{1}}(\boldsymbol{s})=s_{1}s_{2} and \sigma_{2}=\phi^{\boldsymbol{\mu}_{2}}(\boldsymbol{s})=s_{1}s_{3}^{2} , are two independent operators of the rank- 2 ICC of \mathcal{M} . The operator \boldsymbol{\mu}_{3}=(0,0,1) , which defines the third basis element \sigma_{3}=\phi^{\boldsymbol{\mu}_{3}}(\boldsymbol{s})=s_{3} , is an independent operator of the other ICC of \mathcal{M} (which is already in a compact form). Upon the GT \mathcal{T} , the model \mathcal{M} is transformed into the bottom model \mathcal{M}^{\prime} , which appears in a compact form with the rank-2 ICC based solely on the first two variables. Property 35 . Construction of a preferred basis of an MCM. A preferred basis \boldsymbol{b}^{*} of an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} is constructed by combining the elements of a basis \boldsymbol{b}_{\mathcal{M}_{a}} for each ICC \mathcal{M}_{a} : \displaystyle\boldsymbol{b}^{*}=\cup_{a\in\mathcal{A}}\,\boldsymbol{b}_{\mathcal{M}_{a}}\cup\overline{\boldsymbol{b}_{\mathcal{M}}}\,, (119) where \overline{\boldsymbol{b}_{\mathcal{M}}} is a set of (n-r) independent operators that complete the spin basis, with r=\rank(\M) . For each component \mathcal{M}_{a} , any set of r_{a}=\rank(\M_a) independent operators in \mathcal{M}_{a} can be chosen to define the basis \boldsymbol{b}_{\mathcal{M}_{a}}=(\phi^{\boldsymbol{\mu}^{a}_{1}},\cdots,\phi^{\boldsymbol{\mu}^{a}_{r_{a}}}) . The preferred basis of an MCM is therefore not necessarily unique. Using the construction above, any MCM can be represented in a preferred basis, in which the MCM corresponds to a partition of the basis variables, where each part of r_{a} variables identifies an ICC of rank r_{a} . This implies that MCMs with ICCs of the same ranks are related by a GT, because they can be mapped to the same partition in a preferred basis, and therefore they belong to the same equivalence class. This gives the following property, characterizing equivalence classes of MCMs: Property 36 . Equivalence classes of MCMs. Consider an MCM with m ICCs and denote by m_{r_{a}} the number of ICCs of rank r_{a} in the model, such that m=\sum_{r_{a}=1}^{n}m_{r_{a}} . For a given value of q and number of spins n , all the MCMs with the same sequence of multiplicities \{m_{r_{a}}\}_{1\leq r_{a}\leq n} of their ICC ranks are equivalent under gauge transformation, i.e. for any two such model, there exists a GT that can transform one into the other. They all belong to the same equivalence class of MCMs, which is identified by the sequence of multiplicities \{m_{r_{a}}\}_{1\leq r_{a}\leq n} . Proof. We give a sketch of the proof. Consider two MCMs \mathcal{M}_{x} and \mathcal{M}_{y} that have the same sequence of multiplicities \{m_{r_{a}}\}_{1\leq r_{a}\leq n} (i.e., the same rank list \{r_{a}\}_{a\in\mathcal{A}} ). We specify two GTs, \mathcal{T}_{x} for \mathcal{M}_{x} and \mathcal{T}_{y} for \mathcal{M}_{y} , that bring each model into a preferred basis (in which each MCM corresponds to a partition of the basis elements). We design the two GTs such that they map ICCs of the same rank in each model to the same basis elements (for example, an ICC of rank 2 could be mapped to the variables \sigma_{3} and \sigma_{4} for both MCMs). This is possible because the two models have ICCs of the same ranks. As a result, the transformed models \mathcal{T}_{x}[\mathcal{M}_{x}] and \mathcal{T}_{y}[\mathcal{M}_{y}] are identical MCMs (they correspond to the same partition of the basis elements), which means that \mathcal{M}_{x} and \mathcal{M}_{y} are equivalent. Composing the GTs, we can also write that \mathcal{M}_{y}=\mathcal{T}_{y}^{-1}[\mathcal{T}_{x}[\mathcal{M}_{x}]] , where \mathcal{T}_{y}^{-1}\circ\mathcal{T}_{x} is a GT. ∎ As a consequence, the number of different classes of MCMs with the same rank r is obtained by enumerating all possible (unordered) rank list \{r_{a}\}_{a} satisfying the constraint that \sum_{a\in\mathcal{A}}r_{a}=r . This corresponds to all possible integer partitions of r . Property 37 . Number of classes of MCMs of rank r . In a q -state spin system with n spins, the number of equivalence classes of MCMs of rank r (where r\leq n ) is given by the number of integer partitions of r , independently of the value of q . This number is the same as in the binary case 15 , because MCMs of different classes only differ by the rank of their ICCs, independently of the value of q (see Fig. 8 and 11 ). For example, for any integer value of q , there are two equivalence classes of MCMs with rank r=2 (the class of MCMs with two ICCs of rank 1 each, and the class of MCMs with a single ICC of rank 2 ), three equivalence classes for r=3 , and five for r=4 (see complexity landscape in Fig. 11 ). The value of q instead changes the number of MCMs in each equivalence class. Property 38 . Number of MCMs in a class. For a q -state spin system with n spins, the number of models in the class of MCMs defined by the sequence of multiplicities \{m_{r_{a}}\}_{1\leq r_{a}\leq n} (where m_{r_{a}} denotes the number of ICCs of rank r_{a} in the models of the class) is given by (see App. D.3 ): \displaystyle\mathcal{N}_{\rm MCM}(n,\{m_{r_{a}}\}_{1\leq r_{a}\leq n})=\displaystyle\frac{\mathcal{N}_{q}(n,r)}{\displaystyle\prod_{r_{a}=1}^{n}(m_{r_{a}}!)\;\,\mathcal{N}_{q}(r_{a},r_{a})^{m_{r_{a}}}}\;. (120) Here, \mathcal{N}_{q}(n,r) is the number of different ways to choose r independent operators in a q -state spin system with n spins, which is: \displaystyle\mathcal{N}_{q}(n,r)=\begin{cases}\;\;\displaystyle\prod_{i=0}^{r-1}(q^{n}-q^{i})\,,&\qquad{\rm for}\;q\;\textrm{prime},\\[5.0pt] \;\;\displaystyle\prod_{k=1}^{K}p_{k}^{\,(m_{k}-1)n^{2}}\,\prod_{i=0}^{r-1}(p_{k}^{\,n}-p_{k}^{\,i})\,,&\qquad{\rm for}\;q\;\textrm{not prime}.\end{cases} (121) The result for q prime was obtained using the same reasoning as in the binary case 15 . For example, for n=3 and q=3 , there are 117 MCMs with two ICCs of respective rank r_{1}=1 and r_{2}=2 ; Fig. 9 .a shows two of them. The total number of spin models that are MCMs in an n -spin system can be obtained by summing the value in Eq. ( 120 ) over all possible integer partitions of r , for all r from 1 to n . The invariance of the family of MCMs under gauge transformations allows one to approach model selection from a representation invariant perspective, and ultimately design model selection procedures able to capture patterns of the data (such as symmetries, co-dependencies) in a way that is independent of the basis in which the data is initially observed. This is not possible for instance if one restricts the selection to pairwise models, because the family of pairwise spin models is not invariant under gauge transformation. Figure 6 .a gives an example of a GT that transforms a pairwise model into a model with operators of higher order (in this case, there is a 3 -spin operator). 5.3 Statistical properties of MCMs Just like in the binary case 15 , when represented in a preferred basis, an MCM corresponds to a partition of a subset of the basis variables in which each part identifies an ICC: the variables are fully connected inside the parts, with all operators of all orders, and not connected between the parts (see the models in Fig. 9 bottom). The MCM thus completely models all the statistical dependencies within each part (each ICC), but no statistical dependencies at all between the parts, as if they were independent (see Fig. 8 , in the right panel, subspaces of different colors are considered statistically independent by the MCM in the left panel). This peculiar structure of MCMs endows them with properties that make modeling data with MCMs relatively efficient, in comparison to other common modeling approaches. In particular, the independence between the ICCs allows writing the model probability distribution as a product of marginal distributions over each ICC, when expressed in a preferred basis (see Fig. 8 and 10 ). Moreover, the completeness of the ICCs enables a re-parametrization of the components, with which most of the quantities of interest in the context of statistical inference can be easily computed (see next section 5.4 ). Below, we formalize these two properties. When written in a preferred basis, there are no dependencies between the basis variables corresponding to different ICCs of an MCM. This means that the multivariate probability distribution of the MCM factorizes over the basis elements of its ICCs. We recall that a preferred basis \boldsymbol{b}^{*} is a spin basis for the n spin system, which means that it can be used to define a GT \mathcal{T} of the form \boldsymbol{s}^{\prime}=\boldsymbol{b}^{*}(\boldsymbol{s}) (see definition 17 ). Property 39 . Factorization of MCMs over their ICCs. As a consequence of the independence between ICCs, the probability distribution of an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\,\mathcal{M}_{a} factorizes over the probability distributions of its ICCs \mathcal{M}_{a} , when expressed in terms of the operators \boldsymbol{b}^{*}(\boldsymbol{s})=\cup_{a\in\mathcal{A}}\,\boldsymbol{b}_{a}(\boldsymbol{s})\cup\overline{\boldsymbol{b}_{\mathcal{M}}}(\boldsymbol{s}) of a preferred basis of \mathcal{M} (where each \boldsymbol{b}_{a} denotes a basis of the ICC \mathcal{M}_{a} – see property 35 ): p(\boldsymbol{s}\,|\,\boldsymbol{g},\mathcal{M})=\frac{1}{q^{(n-r)}}\,\prod_{a\in\mathcal{A}}\,p_{a}\big(\boldsymbol{b}_{a}(\boldsymbol{s})\,|\,\boldsymbol{g}_{a}^{\prime},\mathcal{M}_{a}^{\prime}\big)\,. (122) Each \mathcal{M}_{a}^{\prime} denotes the ICC \mathcal{M}_{a} represented in terms of the basis variables \boldsymbol{b}_{a}(\boldsymbol{s}) , and each p_{a} is a probability distribution over these r_{a}=\rank(\M_a) spin variables only. The vector \boldsymbol{g}_{a}^{\prime} of parameters of the ICC \mathcal{M}_{a}^{\prime} corresponds to a permutation of the parameters of the vector \boldsymbol{g}_{a} that results from the gauge transformation \boldsymbol{s}^{\prime}=\boldsymbol{b}^{*}(\boldsymbol{s}) (see Def. 19 ). The prefactor corresponds to a uniform distribution over the (n-r) q -state variables not modeled by \mathcal{M} . In equation ( 122 ), we used that for a GT, the probability distribution of the model \mathcal{M}^{\prime}=\mathcal{T}[\mathcal{M}] in the new basis \boldsymbol{s}^{\prime}=\boldsymbol{b}^{*}(\boldsymbol{s}) is related to that of the model \mathcal{M} in the original spin basis \boldsymbol{s} by p(\boldsymbol{s}\,|\,\boldsymbol{g},\mathcal{M})=p(\boldsymbol{s}^{\prime}\,|\,\boldsymbol{g}^{\prime},\mathcal{M}^{\prime}) (see Eq. ( 108 )). For each ICC \mathcal{M}_{a} , the vector \boldsymbol{b}_{a}(\boldsymbol{s}) corresponds to a subset of variables of the new basis \boldsymbol{s}^{\prime}=\boldsymbol{b}^{*}(\boldsymbol{s}) ; it can be interpreted as the transformed state \boldsymbol{s}^{\prime} reduced to the subspace modeled by \mathcal{M}_{a} . The GT \boldsymbol{s}^{\prime}=\boldsymbol{b}^{*}(\boldsymbol{s}) can be written equivalently for the corresponding color variables as the vector-matrix product \boldsymbol{\alpha}^{\prime}=\boldsymbol{\alpha}\,\boldsymbol{T}_{\boldsymbol{b}^{*}} , where \boldsymbol{T}_{\boldsymbol{b}^{*}}=(\boldsymbol{\mu}_{1},\,\dots,\,\boldsymbol{\mu}_{n}) is an n\times n -matrix whose columns are the n operators of the preferred basis \boldsymbol{B}^{*}=\cup_{a\in\mathcal{A}}\boldsymbol{B}_{\mathcal{M}_{a}}\cup\overline{\boldsymbol{B}_{\mathcal{M}}} (see Property 18 ). To use a notation analogous to that used for the spin variables, we denote by \boldsymbol{B}^{*}(\boldsymbol{\alpha})=\boldsymbol{\alpha}\,\boldsymbol{T}_{\boldsymbol{b}^{*}} the vector resulting from the gauge transformation of \boldsymbol{\alpha} into the basis \boldsymbol{B}^{*}=(\boldsymbol{\mu}_{1},\cdots,\boldsymbol{\mu}_{n}) , i.e. \boldsymbol{B}^{*}(\boldsymbol{\alpha})=(\boldsymbol{\alpha}\cdot\boldsymbol{\mu}_{1},\dots,\,\boldsymbol{\alpha}\cdot\boldsymbol{\mu}_{n}) . The gauge transformation can thus be written as \boldsymbol{\alpha}^{\prime}=\boldsymbol{B}^{*}(\boldsymbol{\alpha}) . Similarly, the vector \boldsymbol{B}_{a}(\boldsymbol{\alpha})=(\boldsymbol{\alpha}\cdot\boldsymbol{\mu}^{a}_{1},\dots,\,\boldsymbol{\alpha}\cdot\boldsymbol{\mu}^{a}_{r_{a}}) denotes the transformed state \boldsymbol{\alpha}^{\prime} reduced to the subspace modeled by the ICC \mathcal{M}_{a} . Equation ( 122 ) can then be written in terms of the color variables \boldsymbol{\alpha} as: p(\boldsymbol{\alpha}\,|\,\boldsymbol{g},\mathcal{M})=\frac{1}{q^{(n-r)}}\,\prod_{a\in\mathcal{A}}\,p_{a}\big(\boldsymbol{B}_{a}(\boldsymbol{\alpha})\,|\,\boldsymbol{g}_{a}^{\prime},\mathcal{M}_{a}^{\prime}\big)\,. (123) When written in a preferred basis, each ICC \mathcal{M}_{a} of the MCM is a complete model (see Sec. 2 ) for the sub-system of r_{a} variables \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\alpha}) , where \boldsymbol{B}_{a} is a basis of \mathcal{M}_{a} . This means that \mathcal{M}_{a} can model any possible statistical patterns of the discrete variables \boldsymbol{\alpha}_{a}^{\prime} . The component has (q^{r_{a}}-1) parameters g_{\boldsymbol{\mu}} that fully parametrize the r_{a} -dimensional sub-system and is thus equivalently specified by the (q^{r_{a}}-1) state probabilities p(\boldsymbol{\alpha}_{a}^{\prime}) for all states \boldsymbol{\alpha}_{a}^{\prime}\in[(\mathbb{Z}/q\mathbb{Z})^{r_{a}}]^{*} of the sub-system (the last probability being fixed by normalization, p(\boldsymbol{0})=1-\sum_{\boldsymbol{\alpha}_{a}^{\prime}\neq\boldsymbol{0}}p(\boldsymbol{\alpha}_{a}^{\prime}) ). The ICC \mathcal{M}_{a}^{\prime} can thus be re-written as the following parametric family of probability distributions: \displaystyle p_{a}(\boldsymbol{\alpha}_{a}^{\prime}\,|\,\,\boldsymbol{\eta}_{a},\mathcal{M}_{a}^{\prime})=\sum_{\boldsymbol{\nu}\in[(\mathbb{Z}/q\mathbb{Z})^{r_{a}}]^{*}}\,\eta_{\boldsymbol{\nu}}\,\delta(\boldsymbol{\alpha}_{a}^{\prime}-\boldsymbol{\nu})+\bigg(1-\sum_{\boldsymbol{\nu}\in[(\mathbb{Z}/q\mathbb{Z})^{r_{a}}]^{*}}\eta_{\boldsymbol{\nu}}\bigg)\,\delta(\boldsymbol{\alpha}_{a}^{\prime}-\boldsymbol{0})\,, (124) where each \eta_{\boldsymbol{\nu}} is a parameter that represents the probability that the system is in the state \boldsymbol{\nu}=\boldsymbol{\alpha}_{a}^{\prime} , and \boldsymbol{\eta}_{a} is a vector that contains all the (q^{r_{a}}-1) parameters \eta_{\boldsymbol{\nu}} . Within each ICC, there is therefore a bijection between the (q^{r_{a}}-1) parameters g_{\boldsymbol{\mu}} ’s and \eta_{\boldsymbol{\nu}} ’s (see Sec. 2 ). For any choice of the parameters g_{\boldsymbol{\mu}} ’s of the ICC, the parameters \eta_{\boldsymbol{\nu}} ’s correspond to the state probabilities of the system given by the definition of the complete spin model in Eq. ( 40 ), \eta_{\boldsymbol{\nu}}=p(\boldsymbol{\nu}\,|\,\boldsymbol{g}_{a}^{\prime},\mathcal{M}_{a}^{\prime}) for each state \boldsymbol{\alpha}_{a}=\boldsymbol{\nu} of the sub-system (which corresponds to an inverse discrete Fourier transform). Reciprocally, the parameters g_{\boldsymbol{\mu}} can be obtained from the parameters \eta_{\boldsymbol{\nu}} by the discrete Fourier transform of the log-probabilities, as in Eq. ( 45 ). Property 40 . Equivalent parametrization of ICCs in terms of the state probabilities. As a consequence of the completeness of the ICCs, the probability distribution of an ICC \mathcal{M}_{a} can be equivalently parametrized by the (q^{r_{a}}-1) state probabilities \eta_{\boldsymbol{\alpha}_{a}^{\prime}}=p_{a}\big(\boldsymbol{\alpha}_{a}^{\prime}\,|\,\boldsymbol{g}_{a}^{\prime},\,\mathcal{M}_{a}^{\prime}\big) for all state \boldsymbol{\alpha}_{a}^{\prime}\in[(\mathbb{Z}/q\mathbb{Z})^{r_{a}}]^{*} (one of the state probabilities is fixed by normalization), where \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\alpha}) is the transformed states reduced to the r_{a} -dimensional sub-system modeled by \mathcal{M}_{a}^{\prime} . Figure 10: (colors online) Representation of the model discrete probability distribution in state space for two ICCs of Fig. 9 . Each dot represents a state of the spin system and the color represents the probability of the state. States with the same color have the same probability. Top panel. Representation of the probability distribution of the MCM with a single ICC in Fig. 9 .b. In the best basis, defined as the color variables (\alpha_{1}^{\prime},\alpha_{2}^{\prime}) in the bottom panel of Fig. 9 .b, one can see directly that the model probability distribution factorizes and is uniform along the direction of \alpha_{2}^{\prime} , which gives the state space representation in the top left panel. After the GT (\alpha_{1},\alpha_{2})=\mathcal{T}^{-1}[(\alpha_{1}^{\prime},\alpha_{2}^{\prime})] (top MCM in Fig. 9 .b), the probability distribution remains uniform in the direction of \alpha_{2}^{\prime} , which is perpendicular to the direction of \alpha_{1}^{\prime}=\alpha_{1}+\alpha_{2} . This is a non-trivial factorization when looking at the system of variables (\alpha_{1},\alpha_{2}) . Bottom panel. Representation of the probability distribution of the single ICC based on the spin variables (\sigma_{1},\sigma_{2}) in the bottom panel of Fig. 9 .a. We denote by (\alpha_{1}^{\prime},\alpha_{2}^{\prime},\alpha_{3}^{\prime}) the corresponding color variables of this basis, which is a preferred basis for the ICC, and by (\alpha_{1},\alpha_{2},\alpha_{3}) the basis variables for the top panel of Fig. 9 .a. Independently of the basis representation, the probability distribution for this ICC is uniform in the direction of \alpha_{3}^{\prime} (indicated here by the color remaining identical in this direction), which is perpendicular to the plane defined by \alpha_{1}^{\prime} and \alpha_{2}^{\prime} . The independencies in the model probability distribution (here indicated by the uniform direction) are non-trivial in the basis of the variables (\alpha_{1},\alpha_{2},\alpha_{3}) (bottom right panel), but much easier to see in the basis of the variables (\alpha_{1}^{\prime},\alpha_{2}^{\prime},\alpha_{3}^{\prime}) (bottom left panel). The factorization and completeness properties of MCMs mean that, at best fit, an MCM corresponds to an approximation of the data that neglects all statistical dependencies between the variables of different ICCs and preserves all the other statistical patterns. In the context of model selection, the best MCM for a given dataset therefore corresponds to a factorization of the model probability distribution that best matches the structure of the data, optimally balancing goodness-of-fit of the data against model complexity (methods for this selection are discussed in the next section). This optimal factorization could be in the original basis of the data or in any other gauge-transformed basis (see Fig. 10 ). At best fit, this MCM thus provides a factorization of the empirical distribution that optimally approximates the data, by neglecting statistical dependencies between variables where they are the least relevant (variables assigned to different ICCs) and preserving them where they are the most relevant (within ICCs). In a given basis, the number of possible factorizations over r basis elements corresponds to the number of partitions of these r variables into distinct parts, which is equal to the Bell number of r , denoted B_{r} . The number of different MCMs that factorize in the same preferred basis (denoted MCM^{*} ) is therefore obtained by summing this number over all possible model ranks, from r=0 to n , and accounting for the possible choices of the r basis operators on which the model is based: \displaystyle\mathcal{N}_{MCM^{*}}(n)=\sum_{r=0}^{n}{n\choose r}B_{r}\,. (125) This number doesn’t depend on the value of q and is thus identical to the binary case (see Fig. 8 ). 5.4 Statistical inference and model selection with MCMs A significant advantage of Minimally Complex Models over other parametric models for discrete data is that most useful quantities for statistical modeling have a closed-form analytical expression and are thus cheap to compute numerically. Similarly to the binary case 15 , the factorization property 39 of the model probability distribution implies that the likelihood and the evidence ( 7 ) of an MCM also factorize over the ICCs when written in a preferred basis, and the equivalent parametrization property 40 makes these quantities easy to compute analytically for each ICC. Below, we give closed-form expressions for the maximum likelihood, the geometric complexity appearing in the MDL principle Eq. ( 8 ), and the model evidence ( 7 ). These results (see Appendix D for proofs) are direct extensions of the formulae obtained in the binary case 15 to the more general discrete case. Consider a q -state spin system with n spins represented by the discrete variables \boldsymbol{\alpha}=(\alpha_{1},\cdots,\alpha_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} and a dataset composed of N observations of the system denoted \boldsymbol{\hat{\alpha}}=(\boldsymbol{\alpha}^{(1)},\cdots,\,\boldsymbol{\alpha}^{(N)}) . We assume that the system is stationary and that the observed states are randomly sampled from the same underlying distribution, p(\boldsymbol{\alpha}\,|\,\boldsymbol{g},\,\mathcal{M}) , defined by a parametric model \mathcal{M} . Under this assumption, the probability that the model \mathcal{M} with parameters \boldsymbol{g} assigns to the data, namely the likelihood of the model, is P(\boldsymbol{\hat{\alpha}}\,|\,\boldsymbol{g},\mathcal{M})=\prod_{i=1}^{N}p(\boldsymbol{\alpha}^{(i)}\,|\,\boldsymbol{g},\mathcal{M}) . In the following, we take the model \mathcal{M} to be an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} . We consider a preferred basis of \mathcal{M} of the form \boldsymbol{B}^{*}=\cup_{a\in\mathcal{A}}\,\boldsymbol{B}_{a}\cup\overline{\boldsymbol{B}_{\mathcal{M}}} , where each \boldsymbol{B}_{a} is a basis of the ICC \mathcal{M}_{a} , and denote by \mathcal{M}^{\prime}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a}^{\prime} the representation of \mathcal{M} in this basis (i.e., \mathcal{M}^{\prime}=\mathcal{T}_{\boldsymbol{B}^{*}}[\mathcal{M}] and \mathcal{M}_{a}^{\prime}=\mathcal{T}_{\boldsymbol{B}^{*}}[\mathcal{M}_{a}] for all a\in\mathcal{A} ). We denote by r the rank of \mathcal{M} and by r_{a} the rank of each ICC \mathcal{M}_{a} . Using the factorization Property 39 , the likelihood of an MCM can be written as the product of the likelihood of each ICC, when expressed in a preferred basis: P(\boldsymbol{\hat{\alpha}}\,|\,\boldsymbol{g},\,\mathcal{M})\,=P(\boldsymbol{B}^{*}(\boldsymbol{\hat{\alpha}})\,|\,\boldsymbol{g}^{\prime},\,\mathcal{M}^{\prime})=\frac{1}{q^{N(n-r)}}\prod_{a\in\mathcal{A}}P_{a}\big(\boldsymbol{\hat{\alpha}}_{a}^{\prime}\,|\,\boldsymbol{g}_{a}^{\prime},\,\mathcal{M}_{a}^{\prime}\big)\,, (126) where, for each ICC \mathcal{M}_{a} , \boldsymbol{\hat{\alpha}}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\hat{\alpha}}) denotes the dataset \boldsymbol{\hat{\alpha}} transformed in the basis \boldsymbol{B}^{*} (preferred basis of \mathcal{M} ) and reduced to the basis variables \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\alpha}) (i.e., reduced to the subspace modeled by the ICC). Each term P_{a}\big(\boldsymbol{\hat{\alpha}}_{a}^{\prime}\,|\,\boldsymbol{g}_{a}^{\prime},\,\mathcal{M}_{a}^{\prime}\big)=\prod_{i=1}^{N}p_{a}(\boldsymbol{\alpha}_{a}^{\prime(i)}\,|\,\boldsymbol{g}_{a}^{\prime},\,\mathcal{M}_{a}^{\prime}) is the likelihood of the ICC \mathcal{M}_{a}^{\prime} reduced to the variables \boldsymbol{\alpha}_{a}^{\prime} ; it is a function of the (q^{r_{a}}-1) parameters in the vector \boldsymbol{g}_{a}^{\prime} . Using Property 40 , this likelihood is equivalently parametrized by the (q^{r_{a}}-1) state probabilities \eta_{\boldsymbol{\nu}}=p_{a}\big(\boldsymbol{\nu}\,|\,\boldsymbol{g}_{a}^{\prime},\,\mathcal{M}_{a}^{\prime}\big) , where \boldsymbol{\nu}\in[(\mathbb{Z}/q\mathbb{Z})^{r_{a}}]^{*} denotes the state of the basis variables \boldsymbol{\alpha}_{a}^{\prime} . The likelihood of an ICC expressed in terms of the parameters \eta_{\boldsymbol{\nu}} is then: \displaystyle P_{a}(\boldsymbol{\hat{\alpha}}_{a}^{\prime}\,|\,\boldsymbol{\eta}_{a},\mathcal{M}_{a}^{\prime}) \displaystyle=\prod_{\boldsymbol{\nu}\in(\mathbb{Z}/q\mathbb{Z})^{r_{a}}}\,\eta_{\boldsymbol{\nu}}^{\;\,k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime})}\,, (127) where k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime}) is the number of times the state \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{\nu} occurs in the dataset \boldsymbol{\hat{\alpha}}_{a}^{\prime} , and \boldsymbol{\eta}_{a} denotes the vector of all the parameters \eta_{\boldsymbol{\nu}} of \mathcal{M}_{a}^{\prime} (excluding \eta_{\boldsymbol{0}} which is fixed by normalization). Consequently, the values of the parameters \hat{\boldsymbol{\eta}}_{a}={\rm argmax}_{\boldsymbol{\eta}_{a}}P(\boldsymbol{\hat{\alpha}}_{a}^{\prime}\,|\,\boldsymbol{\eta}_{a},\mathcal{M}_{a}^{\prime}) that best fit the data within each ICC are directly equal to the empirical probabilities: Property 41 . Maximum likelihood estimates. For each ICC \mathcal{M}_{a}^{\prime} , the best fit of the parameters \boldsymbol{\eta}_{a}=\big(\eta_{\boldsymbol{\nu}}\big)_{\boldsymbol{\nu}} is given by the empirical probabilities: \hat{\eta}_{\boldsymbol{\nu}}=\frac{k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime})}{N}\,,\qquad\textrm{for all}\;\boldsymbol{\nu}\in[(\mathbb{Z}/q\mathbb{Z})^{r_{a}}]^{*}\,, (128) where k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime}) is the number of times the state \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{\nu} occurs in the reduced dataset \boldsymbol{\hat{\alpha}}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\hat{\alpha}}) . The bijection between the parameters \boldsymbol{g} and the \boldsymbol{\eta} greatly simplifies the inference step, allowing one to compute the maximum likelihood parameters without having to resort to any parameter fitting (e.g., through gradient descent), which are often computational demanding for high-dimensional models. Replacing these parameter values in the likelihood function ( 127 ), we obtain a closed-form expression for the maximum likelihood of an MCM: Property 42 . Maximum likelihood of MCMs. The maximum likelihood of an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} for a dataset \boldsymbol{\hat{\alpha}} is: P(\boldsymbol{\hat{\alpha}}\,|\,\boldsymbol{\hat{g}},\mathcal{M})=\frac{1}{q^{N(n-r)}}\,\prod_{a\in\mathcal{A}}\left[\prod_{\boldsymbol{\nu}\in\boldsymbol{\hat{\alpha}}_{a}^{\prime}}\,\left(\frac{k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime})}{N}\right)^{\vskip-14.22636ptk_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime})}\right]\,, (129) where the second product is over the distinct states \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{\nu} occurring in the reduced dataset \boldsymbol{\hat{\alpha}}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\hat{\alpha}}) (written in the basis \boldsymbol{B}_{a} of the ICC \mathcal{M}_{a} ) and k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime}) is the number of times they occur. The maximum log-likelihood can then be written as: \log P(\boldsymbol{\hat{\alpha}}\,|\,\boldsymbol{\hat{g}},\mathcal{M})=-N(n-r)\log(q)-N\,\sum_{a\in\mathcal{A}}S(\boldsymbol{\hat{\alpha}}^{\prime}_{a})\,, (130) where S(\boldsymbol{\hat{\alpha}}^{\prime}_{a})=-\sum_{\boldsymbol{\nu}\in\boldsymbol{\hat{\alpha}}_{a}^{\prime}}\,\frac{k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime})}{N}\,\log\left(\frac{k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime})}{N}\right) (131) is the entropy of the dataset \boldsymbol{\hat{\alpha}}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\hat{\alpha}}) (which is a reduction of the original data \boldsymbol{\hat{\alpha}} to the subspace modeled by the ICC \mathcal{M}_{a} ). The maximum log-likelihood in Eq. ( 130 ) can also be obtained more directly by expressing the log-likelihood of each ICC \mathcal{M}_{a} for the system reduced to the variables \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\alpha}) , as minus N times the sum of the entropy of the reduced data S(\boldsymbol{\hat{\alpha}}^{\prime}_{a}) and of the Kullback-Leibler divergence between the ICC and the data. This latter is zero at best fit, because the ICC is complete over the subspace based on the variables \boldsymbol{\alpha}_{a}^{\prime} . A useful quantity for model selection is the model evidence (or marginal likelihood) defined in Eq. ( 7 ). Selecting the model with the largest evidence, instead of the largest maximum likelihood, allows basing the selection of the model not only on the goodness of its fit to the data, but also on its complexity. Within a family of models, the model with the largest evidence achieves an optimal balance between goodness-of-fit and simplicity. Here we compute the evidence assuming Jeffreys’ prior 26 over the parameters (see App. D.9 ). Using the factorization property 39 of MCM, Jeffreys’ prior and the model evidence factorize over the ICCs, and, using the completeness of the ICCs, we obtain a closed-form expression for the model evidence (see App. D.10 ): Property 43 . Evidence (or marginal likelihood) of MCMs. The evidence of an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} is the product of the evidence of each ICC when expressed in a preferred basis \boldsymbol{B}^{*}(\boldsymbol{\alpha})=\cup_{a\in\mathcal{A}}\,\boldsymbol{B}_{a}(\boldsymbol{\alpha})\cup\overline{\boldsymbol{B}_{\mathcal{M}}} of \mathcal{M} : P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M})=\frac{1}{q^{N(n-r)}}\prod_{a\in\mathcal{A}}P_{a}\big(\boldsymbol{B}_{a}(\boldsymbol{\hat{\alpha}})\,|\,\mathcal{M}_{a}^{\prime}\big)\,. (132) Using Jeffreys’ prior, the evidence of each ICC \mathcal{M}_{a}^{\prime} for the reduced dataset \boldsymbol{\hat{\alpha}}^{\prime}_{a}=\boldsymbol{B}_{a}(\boldsymbol{\hat{\alpha}}) is given by (see proof in App. D.10 ): \displaystyle P_{a}(\boldsymbol{\hat{\alpha}}^{\prime}_{a}\,|\,\mathcal{M}_{a}^{\prime})\;=\;\frac{\displaystyle\Gamma\left(\frac{q^{r_{a}}}{2}\right)}{\displaystyle\Gamma\left(N+\frac{q^{r_{a}}}{2}\right)}\;\prod_{\boldsymbol{\nu}\in\boldsymbol{\hat{\alpha}}_{a}^{\prime}}\left(\frac{\displaystyle\,\Gamma\left(k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime})+\frac{1}{2}\right)}{\displaystyle\sqrt{\pi}}\right)\;, (133) where \Gamma denotes the gamma function. The product is over all the distinct states \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{\nu} observed in the reduced dataset \boldsymbol{\hat{\alpha}}_{a}^{\prime} and k_{\boldsymbol{\nu}}(\boldsymbol{\hat{\alpha}}_{a}^{\prime}) is the number of times they occur. For q=2 , we recover the result derived by Ref. 15 in the binary case. The evidence of an ICC in Eq. ( 133 ) only depends on its rank r_{a} , on the empirical distribution of the reduced dataset \boldsymbol{\hat{\alpha}}^{\prime}_{a}=\boldsymbol{B}_{a}(\boldsymbol{\hat{\alpha}}) , and on the number N of datapoints. The evidence of a statistical model is usually expensive to compute from Eq. ( 7 ), due to the high-dimensional integral. Thanks to the closed-form expression ( 133 ), the evidence of any MCM can be computed efficiently with minimal computational resources, making it feasible in practice to perform model selection among MCMs on systems of reasonably large sizes (with hundreds of variables). In Sec. 6 , we apply this approach to real data. Models can also be selected following the minimum description length (MDL) principle 44 ; 43 ; 21 , for which the best model is the one providing the most compressed representation of the data. Equation ( 8 ) gives the description length of a spin model for a sufficiently large number N of samples (expanded to order O(1) in N ). The last term c_{\mathcal{M}} in the expansion is the geometric complexity of the model. It is defined as a high-dimensional integral ( A79 ), which can be computed analytically for MCMs (see App. D.7 ). Property 44 . Geometric complexity of MCMs. Thanks to the independence between ICCs, the geometric complexity of an MCM is given by the sum of the complexity of its ICCs: \displaystyle c_{\mathcal{M}}=\sum_{a\in\mathcal{A}}\,c_{\mathcal{M}_{a}}\,, (134) where the complexity of an ICC only depends on its rank r_{a} and is given by (see proof in App. D.7 ): \displaystyle c_{\mathcal{M}_{a}}=\frac{q^{r_{a}}}{2}\log\pi-\log\Gamma\left(\frac{q^{r_{a}}}{2}\right)\,, (135) where \Gamma is the gamma function. For q=2 , one recovers the result obtained by 9 in the binary case. Figure 11 shows the complexity landscape of MCMs for different values of q . Observe a shift of the entire landscape towards larger complexities for increasing values of q , reflecting the increase in the number of parameters with q . Note the two limit lines, sub-complete models (MCMs with a single ICC) are the simplest among all MCMs with the same number of parameters and rank, while IMCMs are the most complex. For binary systems, Ref. 15 has hypothesized that classes of MCMs are the classes of lowest complexity among models with the same number of parameters and the same rank (hence their name). Although they verified that this is the case for systems with n=4 spins or less, this hypothesis has not been proved in the more general case. However, it is interesting to point out that MCMs likely span a large part of the complexity landscape of all q -state spin models, because they cover a large set of combinations of parameter number and rank. Indeed, at fixed number of parameters, it is expected that the higher the rank of the model (number of degrees of freedom of the model), the higher its complexity 9 . In the binary case, Ref. 9 showed that the sub-complete models are the simplest among all models with the same number of parameters and rank, and the independent models (which are MCMs when q=2 ) are the most complex. Figure 11: (colors online) Complexity c_{\mathcal{M}} of all MCMs with n=4-5 spins for varying values of q . For a given value of q , all the models with the same rank r and rank sequence \{r_{a}\}_{a\in\mathcal{A}} of their ICCs are equivalent. As a consequence, the number of classes of MCMs in an n -spin system is the same for all values of q . Here, one observes the shift in complexity of these classes as one increases the value of q . The two dashed lines indicate the complexity of IMCMs (red) and the complexity of sub-complete models (black). For a large number N of samples, the expansion of the negative log-evidence assuming Jeffreys’ prior matches the expansion of the description length L(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}) in Eq. ( 8 ) 5 ; 38 . In App. D.11 , we verify that this is indeed the case for the closed-form expression ( 133 ) of the log-evidence of MCMs and give the next order term of the expansion. The advantage of using the closed-form expression ( 133 ) of the model evidence over the description length expansion ( 8 ) is that it is exact for any value of N and it is cheap to compute in practice. In particular, it provides an accurate measure for comparing models when the number of datapoints is small or, more precisely, in undersampling cases. 5.5 Measuring data complexity with MCMs The minimum description length (MDL) principle was introduced by Rissanen in the context of measuring the complexity of a noisy dataset. Without compression, a dataset with n q -state discrete variables and N datapoints requires N\times n qits to be encoded, i.e., one qit per variable per datapoint, where one qit corresponds to a unit of information of (\log q) nats (we use the term “qit” for this unit by analogy to bit and trit). Using a statistical model, redundant patterns in the data can be encoded more concisely (encoding the patterns one time instead of multiple times), which yields a compression of the data. The resulting number of qits required to encode a dataset \boldsymbol{\hat{\alpha}} using a statistical model \mathcal{M} is given by the description length L(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}) (taking the logarithm in base q ). The minimum description length achieved (i.e., maximal compression) within a family of statistical models is interpreted by Rissanen 44 as a measure of stochastic complexity of the data, by analogy with algorithmic definitions of complexity (such as Kolmogorov complexity). Extending the parallel between the description length and the negative log-evidence to finite values of N , we propose to use the negative log-evidence of the best MCM as a measure of stochastic complexity of the data within the family of MCMs. In Sec. 6 , we give an example of the application of this quantity as a measure of data complexity. Definition 34 . Complexity of the data. We propose to use the negative log-evidence of the best MCM (which is the MCM with the largest evidence) as a measure of stochastic complexity of the data within the family of MCMs: \displaystyle{\rm COMP}_{MCM}(\boldsymbol{\hat{\alpha}})=-\max_{\mathcal{M}\in{\rm MCM}}\log P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M})\,, (136) where the evidence P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}) of an MCM is given in Property 43 . 6 Applications to real data 6.1 Search algorithms: optimization of the log-Evidence of MCMs Despite the advantage provided by the closed-form expression for the evidence in Eq. ( 133 ), the number of MCMs is still large and in practice searching exhaustively for the best MCM among all remains computationally untractable for systems with more than ten variables. Fortunately however, finding the best MCM (or near-optimal MCM) among those sharing a common preferred basis is computationally accessible, thanks to a direct mapping between these models and partitions of the basis variables. This one-to-one correspondence with partitions allows for the development of efficient search algorithms beyond exhaustive enumeration. In a given preferred basis, finding the best MCM corresponds to finding the factorization of the model probability distribution over the basis variables that best matches the structure of the data. Ref. 1 likens finding such MCM factorization in the original basis of the data to a high-order community detection, and thus is interesting on its own. To simplify the model selection procedure in the binary case, Ref. 15 also hypothesized that the best MCM overall would be obtained in the basis formed by the best independent model (i.e., the one with the largest evidence) and thus proposed to divide the selection procedure in two steps: first find the best independent model and use it as a new basis for the data, and then find an optimal factorization in this basis. We follow a similar approach for the discrete case, focusing on two separate steps: searching for an optimal spin basis and searching for the best MCM in a chosen preferred basis. 6.1.1 Search for the optimal MCM in a given preferred basis In a given preferred basis, each MCM maps to a partition of the spin variables into independent parts, independently of the value of q . This makes it possible to use the same search algorithms as in the binary case, with the only difference being that the model evidence is now computed using the more general formula ( 133 ). Following Ref. 15 , we used two different algorithms: 1) an exhaustive search, going through all possible partitions of the n variables using a Gray code 16 ; 28 , which can be used for small systems with up to about 15 variables; and 2) a greedy search, that starts from the independent model and successively merges the two ICCs that lead to the largest increase in evidence until the evidence reaches a maximum, which can be used for larger systems (our current implementation 14 can be used with up to 128 variables). Ref 14 also implements two other search algorithms not used in this paper, a simulated annealing search and a greedy search using divisive hierarchical clustering. 6.1.2 Search for an optimal basis In the binary case, Ref. 15 proposes to use the best independent model with n operators as a preferred basis for the MCM search. The n independent operators of this model correspond to the spin basis in which the empirical probability distribution is the most likely to factorize over each variable as if there were independent. We extend this idea to the more general discrete case, by searching for a spin basis in which the empirical probability distribution is most likely to factorize. In other words, we search for the best IMCM for the data and any basis for that IMCM equally satisfies the requirement above. Using any of these bases as the preferred basis for the MCM search (in the previous section) will give the same set of MCMs to choose from (because ICCs always include all possible multiples of the basis operators). In the binary case, an IMCM is (also) an independent model, and we recover the approach proposed in 15 . The best IMCM with n ICCs (each of rank 1 ) is defined as the one with the largest evidence. Because all IMCMs with n ICCs are in the same equivalence class, the model with the largest evidence among them is also the one that has the largest maximum likelihood. Using Eq. ( 130 ), the maximum log-likelihood of an IMCM with n ICCs based on the spin basis \boldsymbol{B}=(\boldsymbol{\mu}_{1},\,\dots,\,\boldsymbol{\mu}_{n}) (where each \boldsymbol{B}_{a}=(\boldsymbol{\mu}_{a}) is a basis of one of the ICC) is given by: \displaystyle\log P(\boldsymbol{\hat{\alpha}}\,|\,\boldsymbol{\hat{g}},\mathcal{M}_{\rm imcm})=-N\,\sum_{a=1}^{n}S_{\boldsymbol{\hat{\alpha}}}[\alpha^{\prime}_{a}]\,,\;\;\;{\rm where}\;S_{\boldsymbol{\hat{\alpha}}}[\alpha^{\prime}_{a}]=-\sum_{\alpha_{a}^{\prime}=0}^{q-1}\,\frac{k_{\alpha_{a}^{\prime}}(\boldsymbol{\hat{\alpha}})}{N}\log\left(\frac{k_{\alpha_{a}^{\prime}}(\boldsymbol{\hat{\alpha}})}{N}\right) (137) is the Shannon entropy of the discrete variable \alpha_{a}^{\prime}=\boldsymbol{\mu}_{a}\cdot\boldsymbol{\alpha} in the dataset \boldsymbol{\hat{\alpha}} . Here, the entropy of the reduced dataset S(\boldsymbol{\hat{\alpha}}_{a}^{\prime}) appearing in Eq. ( 131 ) was re-written as S(\boldsymbol{\hat{\alpha}}_{a}^{\prime})=S_{\boldsymbol{\hat{\alpha}}}[\alpha^{\prime}_{a}] because the vector \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\alpha})=(\alpha_{a}^{\prime}) has only one variable. We used the n independent operators \{\boldsymbol{\mu}_{1},\dots,\boldsymbol{\mu}_{n}\} to define the new basis variables \alpha_{a}^{\prime}=\boldsymbol{\mu}_{a}\cdot\boldsymbol{\alpha} for all a\in\{1,\,\dots,\,n\} (see Definition 17 ), and each term k_{\alpha_{a}^{\prime}}(\boldsymbol{\hat{\alpha}}) denotes the number of times \alpha_{a}^{\prime} takes a given value \alpha_{a}^{\prime}\in\{0,\,\dots,\,q-1\} in the dataset \boldsymbol{\hat{\alpha}} (or equivalently the number of times the basis variables \boldsymbol{\alpha}_{a}^{\prime}=\boldsymbol{B}(\boldsymbol{\alpha})=(\alpha_{a}^{\prime}) takes a given value in the transformed and reduced dataset \boldsymbol{\hat{\alpha}}_{a}^{\prime}=\boldsymbol{B}_{a}(\boldsymbol{\hat{\alpha}}) ). Because each state of \alpha_{a}^{\prime} corresponds to a state of the operator \phi^{\boldsymbol{\mu}_{a}}(\boldsymbol{\alpha}) , S_{\boldsymbol{\hat{\alpha}}}[\alpha^{\prime}_{a}] is also the Shannon entropy of the operator \boldsymbol{\mu}_{a} in the data: S_{\boldsymbol{\hat{\alpha}}}[\alpha^{\prime}_{a}]=S_{\boldsymbol{\hat{\alpha}}}[\phi^{\boldsymbol{\mu}_{a}}(\boldsymbol{\alpha})] . Equation ( 137 ) therefore implies that the most likely IMCM is given by the set of the n least entropic independent operators in the data 33 33 33 Note that for q>2 , finding the most likely IMCM is different from finding the most likely independent model. An independent model with n operators can be written as a set of n independent components with one operator in each component, but these components are not complete. This means that, for an independent model, the Kullback-Leibler divergence between the single operator and the data within each independent component is not zero (contrary to IMCMs). This term would then have to be taken into account in the computation of the maximum likelihood of the independent model. . Exactly as in the binary case, finding the most likely IMCM corresponds to finding the set of n independent operators with the lowest entropy. The only difference is that now there are multiple bases of operators that correspond to the same IMCM and thus work equivalently as a preferred basis (they identify the same set of MCMs on that basis). To find these operators for small systems (with n\lesssim 15 ), we extend the exhaustive algorithm of Ref. 15 . We compute the entropy of all the operators of the system (excluding certain operators, listed below) and create an (n\times K) -matrix containing in columns the discrete representations \boldsymbol{\mu}_{j} of the K least entropic operators, ordered from low to high entropy. The elements of this matrix are in (\mathbb{Z}/q\mathbb{Z}) . Identifying the n least entropic independent operators then consists of finding the independent columns in this matrix starting from the left-hand side. This can be done using Gaussian elimination in (\mathbb{Z}/q\mathbb{Z}) : the columns with leading coefficients identify the set of least entropic independent operators. For q non-prime, some interactions are “not invertible” and are directly excluded from this procedure; these are the interactions \boldsymbol{\mu} for which there exists a coefficient c\in(\mathbb{Z}/q\mathbb{Z}) such that c\boldsymbol{\mu}=\boldsymbol{0} in (\mathbb{Z}/q\mathbb{Z})^{n} (see Sec. 4.1 ). Moreover for q>2 , all the considered (invertible) operators \boldsymbol{\mu} have a non-identical complex conjugate -\boldsymbol{\mu} ; conjugate operators have the same empirical entropy and for the preferred basis it doesn’t matter if one uses \boldsymbol{\mu} or -\boldsymbol{\mu} as a basis element because they identify the same preferred basis 34 34 34 It is reassuring that c.c. operators have the same entropy, because they identify the same IMCM. Different entropies would give different values of maximum likelihood ( 137 ) to the same IMCM depending on which operator is used in the basis, which would be problematic. (any partition of the basis elements into ICCs will give the same MCM independently of using \boldsymbol{\mu} or -\boldsymbol{\mu} as a basis element). Therefore, only one element from each conjugate pair is included in the procedure (in our implementation 14 , this is done by keeping only the interaction vectors \boldsymbol{\mu} whose first entry is smaller or equal to q/2 ). Similarly, we can also exclude from the selection all multiples of the already selected operators, because they identify different bases of the same IMCMs 35 35 35 Any partition of the basis elements into ICCs will give the same MCM independently of which operator multiple is used, because ICCs always include all possible multiples of the basis operators. . This wasn’t implemented, but would improve further the speed of the code. With this exhaustive approach, the number of operators to consider grows exponentially as q^{n} , making this algorithm unusable in practice for systems of more than 25 variables. For many real systems, it seems reasonable to assume that the least entropic operators will be of low order (i.e., of order 1, 2, 3, or 4), and one could reduce the exhaustive search to consider operators up to a fixed order k only. In the binary case, Ref. 15 also proposes an iterative algorithm that can consider operators of any order while keeping the computational time similar to fixing k . This algorithm can be easily extended to larger values of q ; it is available in 14 but not used in this paper. Figure 12: MCM analysis of the US Supreme Court data in its original basis for different embeddings. The original dataset is binary and is embedded in the larger q -state space for this analysis. Top. Optimal MCM found by exhaustive search in the original basis of the data for different values of q . The circles represent the 9 justices labeled by their initials: Ruth Bader Ginsburg (RG), John P. Stevens (JS), David Souter (DS), Stephen Breyer (SB), Sandra Day O’Connor (SO), William Rehnquist (WR), Anthony Kennedy (AK), Clarence Thomas (CT), and Antonin Scalia (AS). MCMs are represented as partitions of the basis variables, with components identified by different colors and delimited by dashed lines. The best MCMs for q=2 and q=3 correspond to the same partition. The value of the log-evidence is indicated for each component. The log-evidence of the MCM (reported in Table 2 ) is the sum of the values of its components. Bottom. Scatter plot of the log-evidence of MCMs for all possible partitions of the basis variables, for q=2 (along the horizontal axis) against, respectively, q=3 , 4 and 5 (along the vertical axis). Each dot corresponds to one partition, whose color indicates the number of parts, i.e., the number n_{ICCs} of ICCs of the corresponding MCMs. In each plot, the partition corresponding to the MCM with the largest log-evidence is identified by a red circle for each q ; they are the best MCMs shown in the top panel. The grey circles indicate the partitions corresponding to the best MCMs for smaller values of q . The log-evidence of MCMs corresponding to the same partition decreases with q , due to the increase in complexity penalty. In particular, no partition lies above the (x=y) -line (indicated by the shaded area) and the vertical distance between this line and a dot corresponds to the increase in penalty in the log-evidence when changing q from 2 to, respectively, 3 , 4 , or 5 for the corresponding partition. MCMs with ICCs of the same sizes are penalized by the same amount and corresponds to aligned dots parallel to the (x=y) -line. For the MCMs with n_{ICCs}=2 (orange dots), we indicated the size of the ICCs near the alignment: for example “ [4,5] ” denotes MCMs with one ICC of size 4 and one of size 5. Models with fewer ICCs have a larger average ICC size and thus get a stronger penalty with increasing q (see orange dots moving faster down than other dots from one panel to the next). 6.2 Code availability and reproducibility The codes for all three algorithms can be found in our Python package in Ref. 14 (C++ codes with Python bindings). A notable difference with respect to the codes for binary MCMs provided by Ref. 15 is that datapoints and operators cannot be easily encoded by binary integers anymore. This is because the state vectors \boldsymbol{\alpha} and the interaction vectors \boldsymbol{\mu} are not necessarily binary, but more generally defined in (\mathbb{Z}/q\mathbb{Z})^{n} . To avoid losing efficiency, we encoded these vectors using several 128-bit integers to encode 128 q -state variables (i.e., each q -state variable is encoded by \log_{2}(q) bits). This is to compensate for the lack of built-in data structure to encode integers in base q in our chosen language (C++) but also in most common programming languages. As a proof of concept, we revisit two datasets previously analyzed with MCMs in the binary setting 15 . We study the impact of the choices made for how to discretize the data and of the resolution q of discretization on the structure of the resulting MCM. 6.3 Example 1: binary dataset with artificially increased values of q , embedded in a larger space For illustration purposes, we first analyze a binary dataset using MCMs with varying values of q , as if the (binary) variables were taking values in [0,q-1] . The dataset comes from the US Supreme Court database 49 and consists of the votes of the n=9 justices on N=895 cases debated during the second Rehnquist Court. For q=2 , voting outcomes were labeled as in Ref. 32 using the political inclination (if known) of each debated case, such that a judge casts a vote \alpha_{j}=1 if the decision is conservative-oriented, or \alpha_{j}=0 if it is liberal-oriented. Although the datapoints are binary, one can embed them into the larger state space (\mathbb{Z}/q\mathbb{Z})^{n} , effectively increasing the number of possible configurations while keeping the observed states unchanged. Embedding the data into a larger space is common in data analysis. For instance, when using principal component analysis on discrete data, the data is analyzed as if the variables were taking real values even though they are discrete. 6.3.1 Embedding choice For q>2 , to reflect the opposite political valence between conservative and liberal oriented votes, we gave opposite values of \alpha_{j} to opposite votes, assigning \alpha_{j}=1 to liberal-oriented votes and \alpha_{j}=-1\,(\bmod{q})=(q-1) to conservative-oriented votes. This choice confers conjugate spin values s_{j}=\exp(2 \I\pi\alpha_j/q) to these two states. All the other states of \alpha_{j} are not observed in the data. The specific choice of mapping of \alpha_{j} from binary to discrete values will not impact the outcome of the best MCM in the original basis of the data (compared to any other permutations of the values of \alpha_{j} ). However, it can impact the interactions selected in the best basis (and the interactions of the best spin model overall) and change the interpretation of what a given interaction means (see Sec. 2.4 on interpreting the interactions). Intuitively, we expect that labeling the discrete data in a way that best reflects the meaning associated with the values taken by the variables in the studied system would make it easier to interpret the uncovered interactions. On the other hand, assigning the values at random can make it more difficult to interpret the model. Overall, the final result from the modeling procedure (i.e., the interpreted model) should be consistent across mapping choices. In other words, the uncovered models for different choices should be related mathematically by the (bijective) transformation of variables associated with the different mapping choices). In the following, we first analyze the impact of the embedding on the optimal MCM factorization in the original basis of the data, and then on the overall best MCM. 6.3.2 Optimal MCM factorization in the original basis Figure 12 Top shows the best MCMs found by the exhaustive search in the original basis of the data for varying values of q . For q=3 , we found the same factorization as in the binary case 15 , with the five conservative-oriented justices grouped in one ICC and the four more liberal-oriented justices grouped in a second ICC. Further increasing q breaks these components into smaller ICCs, first splitting the conservative group at q=4 and then the liberal group at q=5 . The reduction of the ICC sizes with larger q can be understood intuitively. For larger values of q , ICCs based on the same number r_{a} of variables require more parameters (precisely, q^{r_{a}}-1 parameters) and are thus more penalized. Because the observed states remain unchanged, we therefore expect the ICCs of the best MCM to get smaller as we artificially increase q . Formally, consider a dataset with variables taking values \boldsymbol{\alpha}\in(\mathbb{Z}/q_{1}\mathbb{Z})^{n} , and consider two MCMs, \mathcal{M}^{q_{1}} and \mathcal{M}^{q_{2}} , corresponding to the same partition of the n basis variables but for two different values of q , respectively q_{1} and q_{2} with q_{2}>q_{1} . For these models, the log-evidence takes the form (using r=n in Eq. ( 132 ) and ( 133 )): \displaystyle\log P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M})=\sum_{a\in\mathcal{A}}\left[\log\frac{\displaystyle\Gamma\left(\frac{q^{r_{a}}}{2}\right)}{\displaystyle\Gamma\left(N+\frac{q^{r_{a}}}{2}\right)}+\sum_{\boldsymbol{\alpha}_{a}\in\boldsymbol{\hat{\alpha}}_{a}}\log\left(\frac{\displaystyle\,\Gamma\left(k_{\boldsymbol{\alpha}_{a}}(\boldsymbol{\hat{\alpha}}_{a})+\frac{1}{2}\right)}{\displaystyle\sqrt{\pi}}\right)\right]\;. (138) Here, \mathcal{A} denotes the common partition identifying both \mathcal{M}^{q_{1}} and \mathcal{M}^{q_{2}} , such that each element a\in\mathcal{A} identifies an ICC in each model based on the same groups of variables \boldsymbol{\alpha}_{a} . Because the dataset itself remains unchanged (with states \boldsymbol{\alpha}\in(\mathbb{Z}/q_{1}\mathbb{Z})^{n} ) and because the two MCMs correspond to the same partition of the basis variables, the second sum in Eq. ( 138 ) takes the same value for both models. Only the complexity part (first term within the first sum) changes with q , becoming more negative for larger q at fixed value of r_{a} . Figure 12 Bottom illustrates how this increase in penalty with q impacts different models. MCMs with ICCs of the same sizes \{r_{a}\} (which belong to the same complexity class) are penalized by the same amount as one increases q (see the alignment of the dots parallel to the (x=y) -line) and the penalty increases faster with q for MCMs with larger average ICC size (i.e. with a smaller number of ICCs). These effects can also be deduced from the dependence in \{r_{a}\} of the complexity term in Eq. ( 138 ). As a result, the best MCM can structurally change when increasing q , favoring models with smaller ICCs (see changing location of the red circle towards MCMs with smaller ICCs). 6.3.3 Best MCM factorization overall Figure 13 shows the best MCM found overall for different values of q , by performing first an exhaustive search for the optimal basis, and then an exhaustive search for the optimal MCM on that basis. The nine independent operators of the best basis are represented by squares in the figure. Except for one single spin operator on AS, all these operators are pairwise and identify interactions between the same pairs of justices for all values of q . In the binary case, 15 reported that these 9 interactions alone account for 86\% of the information extracted by a fully connected pairwise model with 45 interactions. A notable difference with the binary case, is that these pairwise operators are of the form \boldsymbol{\mu}_{ij}=(1,\,q-1) between two justices i and j , and not of the form \boldsymbol{\mu}_{ij}=(1,\,1) as one could have naively extrapolated from the binary case (where \boldsymbol{\mu}_{ij} denotes the interaction vector \boldsymbol{\mu} reduced to the i -th and j -th entries). This is because the most frequent pattern between these pairs of justices is the symmetric voting pattern \alpha_{i}=\alpha_{j} , which is a pattern that is best captured by this type of pairwise interaction (see the explanations in Example 7 of Sec. 2.4.2 ). Indeed, the justices SO and SB, whose interaction is the most entropic pairwise interaction in the basis, vote identically in 78\% of the cases, and AS and CT, whose pairwise interaction is the least entropic interaction among all, vote identically in 93\% of the cases. Note that the choice of embedding doesn’t impact the best basis in this case, because the symmetric patterns \alpha_{i}=\alpha_{j} identified by the best basis remain unchanged under permutation of the state values. In Fig. 13 , the basis operators are numbered from the least to the most entropic. Observe that this ordering changes slightly from q=2 to q=3 (see the operators ranked 7 and 8, and 2 and 3). This is because for q=2 the entropy of an operator only depends on the probability of the operator to be even (symmetric state \alpha_{i}=\alpha_{j} ) or odd (antisymmetric states \alpha_{i}=-\alpha_{j} ), while for q\geq 3 the entropy of a pairwise operator also depends on the relative occurrence of the non-symmetric states. The ICCs of the best MCMs found on the optimal basis for each q are identified by the triangles in Fig. 13 . These MCMs have ICCs of smaller sizes (on average) than those found in the original basis for the same value of q (shown in Fig. 12 ), which means that they correspond to less complex models (with fewer interactions). The log-evidence of these models (see table 2 ) is also larger than that of the MCMs based on the original basis. This means that they are better models for the data, which is what we expected from the two-step procedure. Similarly to the analysis in the original basis, ICCs are smaller for larger q , which can be explained by the increase in penalty with q while the data patterns remain mostly unchanged. ICCs for larger q also seem to lie mostly within the ICCs for smaller q , although this doesn’t hold for all ICCs. Figure 13: Factor graph representation of the best MCM found by exhaustive search for the US Supreme Court dataset for different values of q . The circles represent the original variables, which correspond to the 9 justices labeled by their initials as in Fig. 12 . The squares represent the operators of the best basis found by exhaustive search, numbered from low to high entropy. For each basis operators (squares), the colored lines indicate which “justice” variables (circles) are included in the operator and the color specifies the power to which each variable is raised: one in blue, two in red, three in green, and four in orange. For example, for q=3 , the basis operator of lowest entropy (square with number “ 0 ”) is the operator \phi_{0}(\boldsymbol{s})=s^{\,}_{CT}\,s^{2}_{AS} . The triangles represent the ICCs of the best MCM, a line from an operator to a component identify the presence of that operator in the component. 6.4 Example 2: Choice of discretization and standardization of discrete data. In this second example, we analyze answers to the Big Five Personality Test 18 . In particular, we discuss possible choices of discretization schemes and their impact on the best MCM factorization in the original basis. The test consists of n=50 questions designed to probe the personality of the respondents along five dimensions generally considered as describing the main traits of personality: extraversion, emotional stability, agreeableness, conscientiousness, and openness to experience. Each trait is measured based on the answers to ten statements on a scale of x=1 (disagree) to 5 (agree). For example, extraversion is probed by statements such as “I am the life of the party” or “I am quiet around strangers” . We obtained a dataset from the Open-Source Psychometrics Project 4 with answers from N=602\,591 individuals (after cleaning for errors and identical IP addresses). The dataset was then converted from the original 1-to-5 scale to the desired discrete formats, with respectively q=2 , 3 , or 5 , using two different discretization schemes. In the following, we only perform the MCM analysis in the original basis of the data. This is because we are mainly interested in studying the impact of different choices of discretization of the data and the original variables were purposely chosen in the design of the Big Five test. As a side note, in the binarized version, 15 found that the best MCM in the best basis happened to be is identical to the best MCM found in the original basis. 6.4.1 Discretization Scheme 1: direct mapping For the first scheme, we re-assign the values of the variables x_{j}\in\{1,\,2,\,3,\,4,\,5\} in the original data (where x_{j} denotes the answer to the j -th question) to new discrete values \alpha_{j}\in(\mathbb{Z}/q\mathbb{Z}) for q=2,\,3 and 5 , as described in Table 1 Scheme 1. To respect the opposite valence between positive and negative answers, we associated the “neutral” answer to \alpha_{j}=0 and gave opposite values 36 36 36 corresponding to conjugate values of s_{j}=\exp(2 i \pi\alpha_j/q) to opposite answers (e.g., \alpha_{j}=1 to “agree” and \alpha_{j}=-1\,({\rm mod}\,q)=(q-1) to “disagree”). Choosing this assignment of \alpha_{j} doesn’t affect the outcome of the best MCM with respect to selecting any other permutations of the values of \alpha_{j} (because permuting the values of \alpha_{j} doesn’t change the numbers k_{\boldsymbol{\alpha}_{a}} of occurrence of the states used in Eq. ( 138 )). However, as mentioned previously, if the final goal is to obtain a more precise high-order spin model for the data (e.g., beyond MCMs), then different choices can lead to different optimal models, and a choice informed by domain knowledge can make it easier to interpret the uncovered model. Figure 14 shows the best MCMs found in the original basis of the data for Scheme 1. From q=2 to q=3 , the sizes of the ICCs remain large with 9 to 10 variables: the dataset is sufficiently rich at q=3 for the balance between fitting and complexity to require ICCs of a similar sizes than at q=2 (contrary to Example 1). In other words, the increase in size of the state space is compensated by an increase in richness of the data. From q=3 to q=5 , the ICCs break down into smaller components. Although questions are mostly grouped into ICCs corresponding to the same traits, we also find mismatches (especially for larger q ). Additionally, we observe that some statements are more biased than others towards agreeing or disagreeing (e.g., “I insult others”), which may give rise to spurious correlations. The next scheme will attempt to reduce this effect by standardizing the data. 6.4.2 Discretization Scheme 2: standardization In the second scheme, the value of each variable x_{j} was re-centered around its empirical mean \bar{x_{j}} following Scheme 2 in Table 1 . Besides, for q=3 and 5 , we defined small intervals on the values of x_{j} of size 2\sigma_{j}\,\epsilon within which \alpha_{j} takes a constant value, where \sigma_{j} denotes the standard deviation of x_{j} . The value of \epsilon was then adjusted to maximize the entropy of the variables in the data (see Fig. A2 in Appendix). Here as well, we reflected the opposite valence of the data between positive and negative answers by giving opposite values of \alpha_{j} to opposite intervals in x_{j} . The introduction of Scheme 2 is motivated by the observation that some statements are significantly more biased than others. For example, the answer to the statement “ I insult others ” is more often negative, with 62\% of the respondents who disagree and only 21\% who agree ( \bar{x}_{j}\simeq 2.27 ). However, such patterns are inherent to the choice of the question, and are not directly informative about personality. Instead, one may understand personality from the way respondents answer with respect to the average behavior in the population. In this context, it would be more interesting to model patterns between answers based on their deviation from the population average instead of raw dependencies. We achieved this in Scheme 2 by standardizing each variable and maximizing their entropy before modeling them, so that individual variables carry as little information as possible. For example, staying “neutral” for the statement “ I insult others ” ( 17\% of the respondents) tends to be more negative than the majority of people, and recentering the data will then move “neutral” answers to the negative side. Similarly, the statement “ I spend time reflecting on things ” has the lowest entropy (see Fig. A2 in Appendix), with 48\% of the respondents “strongly agreeing“ and 34\% “agreeing“ ( \bar{x}_{j}\simeq 4.22 ); recentering the data will then give “neutral“ answers to respondents “agreeing“ in their response. Figure 14 shows the best MCMs found in the original basis of the data for Scheme 2. They reveal a clearer separation of the five traits than in Scheme 1, in particular for q=3 and 5 . In this example, reducing the bias of the variables allows us to better focus the model on the (high-order) correlation structure of the data, following a principle similar to using z -scored variables in Principal Component Analysis and revealing in this case a clearer separation between the traits. We note that the standardization of the data is not a requirement of the technique, but is a specific choice that can be made depending on what type of dependencies one is interested in modeling (i.e., row dependencies or correlations). Table 1: Discretization schemes for the Big Five Personality Test data. In the original dataset, the answers x_{i} to the i -th statement can take five different values: 1 (disagree), 2 (slightly disagree), 3 (neutral/no opinion), 4 (slightly agree), and 5 (agree). The table gives the two mapping schemes we used between the values of the original variable x_{i} and the new variable \alpha_{i} for each value of q , where \bar{x}_{i} and \sigma_{i} are respectively the empirical average and the standard deviation of x_{i} and \epsilon is a parameter. \alpha_{i} x_{i} in Scheme 1 x_{i} in Scheme 2 q=2 1 1-2: (slightly) disagree x_{i}<\bar{x}_{i} 0 ( 50\% )  or 1 (50%) 3 : neutral 0 4 - 5 : (slightly) agree \bar{x}_{i}m} in which, for the case k>m , we used that [\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})]^{q}=1 for all \boldsymbol{\alpha},\boldsymbol{\mu} . For the double sum with km , the exponent (m-k) is in the interval [-(q-1),-1] for all the terms in the sum, and, by adding q , we get that the exponent (q+m-k)\in[1,q-1] . In the following, we make the change of variables r=(q+m-k) replacing k by r . \displaystyle e^{\;g_{\boldsymbol{\mu}}\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})+g_{\boldsymbol{\mu}}^{*}\phi^{-\boldsymbol{\mu}}(\boldsymbol{\alpha})}=\underbrace{\sum_{m=0}^{q-1}c_{m}(g_{\boldsymbol{\mu}})c_{m}(g_{\boldsymbol{\mu}}^{*})}_{k=m}+\underbrace{\sum_{m=0}^{q-1}\sum_{r=1}^{m}c_{m}(g_{\boldsymbol{\mu}})c_{m-r}(g_{\boldsymbol{\mu}}^{*})\left[\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})\right]^{r}}_{km} Note that the coefficient in front of [\phi^{\boldsymbol{\mu}}]^{r} in each term can be written under the form: c_{m}(g_{\boldsymbol{\mu}})c_{(m-r)\bmod{q}}(g_{\boldsymbol{\mu}}^{*}) . Indeed, in the first double sum, the values taken by m and r are such that (m-r)\in[0,q-1] , and thus (m-r)\bmod{q}=(m-r) . In the second double sum, the values taken by m and r are such that (m-r)\in[-(q-1),-1] , and thus (m-r)\bmod{q}=q+(m-r) . This gives: \displaystyle e^{\;g_{\boldsymbol{\mu}}\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})+g_{\boldsymbol{\mu}}^{*}\phi^{-\boldsymbol{\mu}}(\boldsymbol{\alpha})}=\sum_{m=0}^{q-1}\sum_{r=0}^{q-1}c_{m}(g_{\boldsymbol{\mu}})c_{(m-r)\bmod{q}}(g_{\boldsymbol{\mu}}^{*})\left[\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})\right]^{r}\,, (A33) which finally gives Eq. ( 63 ) after switching the order of the two sums. ∎ B.4 Loop expansion of the partition function Proof of Property 9 . Consider a model \mathcal{M}\subseteq(\mathbb{Z}/q\mathbb{Z})^{n} . We denote by K=|\mathcal{M}| the number of operators in the model and arbitrarily index the operators from 1 to K : \mathcal{M}=\{\boldsymbol{\mu}_{1},\,\cdots,\,\boldsymbol{\mu}_{K}\} . Using the generalized Euler formula ( A25 ) in the expression of the partition function ( 21 ): \displaystyle Z_{\mathcal{M}}(\boldsymbol{g}) \displaystyle=\sum_{\boldsymbol{\alpha}}\prod_{\boldsymbol{\mu}\in\mathcal{M}}\left(\sum_{r=0}^{q-1}c_{r}(g_{\boldsymbol{\mu}})\,\left[\phi^{\boldsymbol{\mu}}(\boldsymbol{\alpha})\right]^{r}\right)\,,\qquad{\rm where}\;\;c_{r}(x)=\sum_{k\geq 0}\frac{x^{kq+r}}{(kq+r)!}\,, (A34) \displaystyle=\sum_{\boldsymbol{\alpha}}\sum_{\boldsymbol{r}\in(\mathbb{Z}/q\mathbb{Z})^{K}}\prod_{k=1}^{K}\big[c_{r_{k}}(g_{\boldsymbol{\mu}_{k}})\,\left[\phi^{\boldsymbol{\mu}_{k}}(\boldsymbol{\alpha})\right]^{r_{k}}\big]\,, (A35) in which r_{k} denotes the k -th element of the vector \boldsymbol{r} . Using that [\phi^{\boldsymbol{\mu}}]^{r}(\boldsymbol{\alpha})=\phi^{r\boldsymbol{\mu}}(\boldsymbol{\alpha}) and that \phi^{\boldsymbol{\mu}_{i}}(\boldsymbol{\alpha})\phi^{\boldsymbol{\mu}_{j}}(\boldsymbol{\alpha})=\phi^{\boldsymbol{\mu}_{i}+\boldsymbol{\mu}_{j}}(\boldsymbol{\alpha}) , where the sum and product in the exponents are taken over (\mathbb{Z}/q\mathbb{Z})^{n} , one gets: \displaystyle Z_{\mathcal{M}}(\boldsymbol{g}) \displaystyle=\sum_{\boldsymbol{r}\in(\mathbb{Z}/q\mathbb{Z})^{K}}\left(\prod_{k=1}^{K}c_{r_{k}}(g_{\boldsymbol{\mu}_{k}})\right)\,\sum_{\boldsymbol{\alpha}}\phi^{\sum_{k=1}^{K}r_{k}\boldsymbol{\mu}_{k}}(\boldsymbol{\alpha})\,, (A36) Observing that, due to Property ( 2 ), \displaystyle\sum_{\boldsymbol{\alpha}}\phi^{\sum_{k=1}^{K}r_{k}\boldsymbol{\mu}_{k}}(\boldsymbol{\alpha})=\begin{cases}\;\;q^{n}\,,\qquad&{\rm if}\;\;\sum_{k=1}^{K}r_{k}\boldsymbol{\mu}_{k}=\boldsymbol{0}\qquad\textrm{in }(\mathbb{Z}/q\mathbb{Z})^{n}\\ \;\;0\,,\qquad&{\rm else}\,,\end{cases} (A37) we define the loops of \mathcal{M} as the vectors \boldsymbol{r}=(r_{1},\,\dots,\,r_{K}) for which this sum is non-zero. The set of loops of a model \mathcal{M} is then: \displaystyle\boxed{\qquad\mathcal{L}_{q}(\mathcal{M})=\bigg\{\boldsymbol{\ell}\in(\mathbb{Z}/q\mathbb{Z})^{K}\;\Big|\;\sum_{k=1}^{K}\ell_{k}\,\boldsymbol{\mu}_{k}=\boldsymbol{0}\bigg\}\;,\qquad} (A38) and, the partition function can be computed as a sum over the loops of the model as: \displaystyle\boxed{\qquad Z_{\mathcal{M}}(\boldsymbol{g})=q^{n}\,\sum_{\boldsymbol{\ell}\in\mathcal{L}_{q}(\mathcal{M})}\prod_{k=1}^{K}c_{\ell_{k}}(g_{\boldsymbol{\mu}_{k}})\,,\qquad{\rm where}\;\;c_{\ell}(x)=\sum_{k\geq 0}\frac{x^{kq+\ell}}{(kq+\ell)!}\,.\qquad} (A39) ∎ B.5 Loop expansion without trivial loops from c.c. operators Proof of Property 10 . Consider a spin model \mathcal{M}\subseteq(\mathbb{Z}/q\mathbb{Z})^{n} , which we write under the form \mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} as described in Definition 10 . We denote K_{0}=|\mathcal{M}_{0}| and K_{1}=|\mathcal{M}_{1}| the number of operators respectively in \mathcal{M}_{0} and in \mathcal{M}_{1} and arbitrarily index the operators: \displaystyle\mathcal{M}_{0}=\{\boldsymbol{\mu}_{0,1},\cdots,\,\boldsymbol{\mu}_{0,K_{0}}\}\qquad{\rm and}\qquad\mathcal{M}_{1}=\{\boldsymbol{\mu}_{1,1},\cdots,\,\boldsymbol{\mu}_{1,K_{1}}\}\,. (A40) Let’s replace Eq. ( 63 ) and Eq. ( 65 ) in the expression of Z_{\mathcal{M}} from Eq. ( 62 ): \displaystyle Z_{\mathcal{M}}(\boldsymbol{g}) \displaystyle=\sum_{\boldsymbol{\alpha}}\prod_{\boldsymbol{\mu}_{0}\in\mathcal{M}_{0}}\Big[A_{0}(g_{\boldsymbol{\mu}_{0}})+A_{1}(g_{\boldsymbol{\mu}_{0}})\;\phi^{\boldsymbol{\mu}_{0}}(\boldsymbol{\alpha})\Big]\prod_{\boldsymbol{\mu}_{1}\in\mathcal{M}_{1}}\left[\,\sum_{r=0}^{q-1}B_{r}(g_{\boldsymbol{\mu}_{1}})\left[\phi^{\boldsymbol{\mu}_{1}}(\boldsymbol{\alpha})\right]^{r}\,\right] (A41) \displaystyle=\sum_{\boldsymbol{\alpha}}\Bigg[\sum_{\boldsymbol{r}_{0}\in(\mathbb{Z}/2\mathbb{Z})^{K_{0}}}\prod_{i=1}^{K_{0}}\left(A_{r_{0,i}}(g_{\boldsymbol{\mu}_{0,i}})\,[\phi^{\boldsymbol{\mu}_{0,i}}(\boldsymbol{\alpha})]^{r_{0,i}}\right)\Bigg]\Bigg[\sum_{\boldsymbol{r}_{1}\in(\mathbb{Z}/q\mathbb{Z})^{K_{1}}}\prod_{j=1}^{K_{1}}\left(B_{r_{1,j}}(g_{\boldsymbol{\mu}_{1,j}})\,[\phi^{\boldsymbol{\mu}_{1,j}}(\boldsymbol{\alpha})]^{r_{1,j}}\right)\Bigg]\,, (A42) where r_{0,i} (resp. r_{1,i} ) denotes the i -th element of the vector \boldsymbol{r}_{0} (resp. \boldsymbol{r}_{1} ). We use that [\phi^{\boldsymbol{\mu}}]^{r}(\boldsymbol{\alpha})=\phi^{r\boldsymbol{\mu}}(\boldsymbol{\alpha}) and that \phi^{\boldsymbol{\mu}_{i}}(\boldsymbol{\alpha})\phi^{\boldsymbol{\mu}_{j}}(\boldsymbol{\alpha})=\phi^{\boldsymbol{\mu}_{i}+\boldsymbol{\mu}_{j}}(\boldsymbol{\alpha}) , where the operations in the exponents are taken over (\mathbb{Z}/2\mathbb{Z})^{n} if \boldsymbol{\mu}\in\mathcal{M}_{0} and over (\mathbb{Z}/q\mathbb{Z})^{n} if \boldsymbol{\mu}\in\mathcal{M}_{1} . This leads to: \displaystyle Z_{\mathcal{M}}(\boldsymbol{g}) \displaystyle=\sum_{\boldsymbol{r}_{0}\in(\mathbb{Z}/2\mathbb{Z})^{K_{0}}}\sum_{\boldsymbol{r}_{1}\in(\mathbb{Z}/q\mathbb{Z})^{K_{1}}}\left[\prod_{i=1}^{K_{0}}A_{r_{0,i}}(g_{\boldsymbol{\mu}_{0,i}})\prod_{j=1}^{K_{1}}B_{r_{1,j}}(g_{\boldsymbol{\mu}_{1,j}})\right]\sum_{\boldsymbol{\alpha}}\phi^{\sum_{i=0}^{K_{0}}r_{0,i}\boldsymbol{\mu}_{0,i}+\sum_{j=0}^{K_{1}}r_{1,j}\boldsymbol{\mu}_{1,j}}(\boldsymbol{\alpha})\,. (A43) Using that (see Property 2 ): \displaystyle\sum_{\boldsymbol{\alpha}}\phi^{\sum_{i=0}^{K_{0}}r_{0,i}\boldsymbol{\mu}_{0,i}+\sum_{j=0}^{K_{1}}r_{1,j}\boldsymbol{\mu}_{1,j}}(\boldsymbol{\alpha})=\begin{cases}\;\;q^{n}\,,\qquad&{\rm if}\;\;\sum_{i=0}^{K_{0}}r_{0,i}\boldsymbol{\mu}_{0,i}+\sum_{j=0}^{K_{1}}r_{1,j}\boldsymbol{\mu}_{1,j}=\boldsymbol{0}\qquad\textrm{in }(\mathbb{Z}/q\mathbb{Z})^{n}\\ \;\;0\,,\qquad&{\rm else.}\end{cases} (A44) we defined the set of (non-trivial) loops of a model \mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} as: \displaystyle\boxed{\qquad\mathcal{L}_{q}^{cc}(\mathcal{M}_{0},\mathcal{M}_{1})=\bigg\{(\boldsymbol{r}_{0},\boldsymbol{r}_{1})\in(\mathbb{Z}/2\mathbb{Z})^{K_{0}}\times(\mathbb{Z}/q\mathbb{Z})^{K_{1}}\;\Big|\;\sum_{i=1}^{K_{0}}r_{0,i}\,\boldsymbol{\mu}_{0,i}+\sum_{j=1}^{K_{1}}r_{1,j}\,\boldsymbol{\mu}_{1,j}=\boldsymbol{0}\bigg\}\;.\qquad} (A45) Finally, the partition can be computed as a sum over these loops, as: \displaystyle\boxed{\qquad Z_{\mathcal{M}}(\boldsymbol{g})=q^{n}\,\sum_{(\boldsymbol{r}_{0},\boldsymbol{r}_{1})\in\mathcal{L}_{q}^{cc}(\mathcal{M}_{0},\mathcal{M}_{1})}\prod_{i=1}^{K_{0}}A_{r_{0,i}}(g_{\boldsymbol{\mu}_{0,i}})\prod_{j=1}^{K_{1}}B_{r_{1,j}}(g_{\boldsymbol{\mu}_{1,j}})\,,\qquad} (A46) \displaystyle{\rm where}\qquad A_{0}(g_{\boldsymbol{\mu}})=\sum_{k=0}^{\frac{q}{2}-1}c_{2k}(g_{\boldsymbol{\mu}})\qquad{\rm and}\qquad A_{1}(g_{\boldsymbol{\mu}})=\sum_{k=0}^{\frac{q}{2}-1}c_{2k+1}(g_{\boldsymbol{\mu}})\,, (A47) \displaystyle B_{r}(g_{\boldsymbol{\mu}})=\sum_{m=0}^{q-1}c_{m}(g_{\boldsymbol{\mu}})\,c_{(m-r)\bmod{q}}(g^{*}_{\boldsymbol{\mu}})\,,\qquad{\rm and}\qquad c_{r}(x)=\sum_{k\geq 0}\frac{x^{kq+r}}{(kq+r)!}\,. (A48) ∎ For systems with q prime or q=2\,p where p is prime, the contribution from the independent part of a model \mathcal{M} (strong and weak) can be directly identified from this last expression, as the term in the sum for which (\boldsymbol{\ell}_{0},\boldsymbol{\ell}_{1})=(\boldsymbol{0},\boldsymbol{0}) : \displaystyle Z_{\mathcal{M}_{ind}}(\boldsymbol{g}) \displaystyle=q^{n}\,\prod_{\boldsymbol{\mu}_{0}\in\mathcal{M}_{0}}A_{0}(g_{\boldsymbol{\mu}_{0}})\,\prod_{\boldsymbol{\mu}_{1}\in\mathcal{M}_{1}}B_{0}(g_{\boldsymbol{\mu}_{1}})\,, (A49) \displaystyle{\rm where}\;A_{0}(x)=\cosh(x)\qquad{\rm and}\qquad B_{0}(x)=\sum_{m=0}^{q-1}c_{m}(x)\,c_{m}(x^{*})\,. (A50) Note that c_{m}(x^{*})=[c_{m}(x)]^{*} and thus c_{m}(x)\,c_{m}(x^{*})=\lVert c_{m}(x)\rVert^{2} . Appendix C Gauge transformations C.1 Counting gauge transformations We give the main lines of the proof of Eq. ( 93 ). The group of gauge transformations \mathcal{G}_{q}(n) is given by the general linear group GL((\mathbb{Z}/q\mathbb{Z})^{n}) . We can compute the number of gauge transformations using the Chinese Remainder Theorem. Let the prime factorization of q be q=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}} . The ring \mathbb{Z}/q\mathbb{Z} is then isomorphic to the product of rings \prod_{i=1}^{k}\mathbb{Z}/p_{i}^{a_{i}}\mathbb{Z} . This induces a group isomorphism: \displaystyle GL((\mathbb{Z}/q\mathbb{Z})^{n})\cong\prod_{i=1}^{k}GL((\mathbb{Z}/p_{i}^{a_{i}}\mathbb{Z})^{n})\,. (A51) It follows that \displaystyle|GL((\mathbb{Z}/q\mathbb{Z})^{n})|=\prod_{i=1}^{k}|GL((\mathbb{Z}/p_{i}^{a_{i}}\mathbb{Z})^{n})|\,. (A52) It remains to determine the order of GL((\mathbb{Z}/p^{a}\mathbb{Z})^{n}) for a prime p and a\in\mathbb{N} . Consider the canonical ring homomorphism \rho:GL((\mathbb{Z}/p^{a}\mathbb{Z})^{n})\to GL((\mathbb{Z}/p\mathbb{Z})^{n}) which reduces each matrix entry modulo p . This map is a surjective group homomorphism. By the first isomorphism theorem for groups, we have: \displaystyle|GL((\mathbb{Z}/p^{a}\mathbb{Z})^{n})|=|\ker(\rho)|\cdot|GL((\mathbb{Z}/p\mathbb{Z})^{n})|\,. (A53) The kernel, \ker(\rho) , consists of matrices M\in GL((\mathbb{Z}/p^{a}\mathbb{Z})^{n}) such that M\equiv I\pmod{p} , where I is the identity matrix. Any such matrix can be written in the form M=I+pA , where A is an n\times n matrix with entries in \mathbb{Z}/p^{a-1}\mathbb{Z} . There are (p^{a-1})^{n^{2}} possible matrices for A . Therefore, the order of the kernel is: \displaystyle|\ker(\rho)|=(p^{a-1})^{n^{2}}=p^{n^{2}(a-1)}\,. (A54) The remaining term, |GL_{n}(\mathbb{Z}/p\mathbb{Z})| , is the order of the general linear group over the finite field \mathbb{F}_{p} . This is a standard result obtained by counting the ways to choose n linearly independent column vectors from \mathbb{F}_{p}^{n} . The formula is: \displaystyle|GL(\mathbb{F}_{p}^{n})|=(p^{n}-1)(p^{n}-p)\cdots(p^{n}-p^{n-1})=\prod_{k=0}^{n-1}(p^{n}-p^{k})\,. (A55) Combining these results, the order for the prime power case is: \displaystyle|GL_{n}(\mathbb{Z}/p^{a}\mathbb{Z})|=p^{n^{2}(a-1)}\prod_{k=0}^{n-1}(p^{n}-p^{k})\,. (A56) The total number of gauge transformations for an arbitrary q is found by substituting this into the product over the prime factors of q . C.2 Gauge transformation of a spin model Consider a spin model \mathcal{M} with parameters \boldsymbol{g} . Under a gauge transformation \mathcal{T}_{\boldsymbol{b}} , the energy of a state \boldsymbol{s} in the model can be rewritten in terms of the new basis variables \boldsymbol{s}^{\prime} , by using the inverse GT \boldsymbol{s}=\boldsymbol{b}^{-1}(\boldsymbol{s}^{\prime}) : \displaystyle H(\boldsymbol{s}\mid\boldsymbol{g},\,\mathcal{M}) \displaystyle=\sum_{\boldsymbol{\mu}\in\mathcal{M}}g_{\boldsymbol{\mu}}\,\phi^{\boldsymbol{\mu}}(\boldsymbol{s})=\sum_{\boldsymbol{\mu}\in\mathcal{M}}g_{\boldsymbol{\mu}}\,\phi^{\boldsymbol{\mu}}(\boldsymbol{b}^{-1}(\boldsymbol{s}^{\prime}))=\sum_{\boldsymbol{\mu}\in\mathcal{M}}g_{\boldsymbol{\mu}}\,\mathcal{T}_{\boldsymbol{b}}[\phi^{\boldsymbol{\mu}}](\boldsymbol{s}^{\prime})\,, (A57) where we used the definition of gauge transformed operators ( 95 ) in the last equality. Because the transformation of a spin operator \mathcal{T}_{\boldsymbol{b}}[\phi^{\boldsymbol{\mu}}] is still a spin operator (see Definition 18 ), the last expression in Eq. ( A57 ) corresponds to the Hamiltonian of a spin model with operators \mathcal{T}_{\boldsymbol{b}}[\phi^{\boldsymbol{\mu}}](\boldsymbol{s}^{\prime})=\phi^{\boldsymbol{\mu}^{\prime}}(\boldsymbol{s}^{\prime}) where \boldsymbol{\mu}^{\prime}=\boldsymbol{T}^{-1}\boldsymbol{\mu} . The energy of a state \boldsymbol{s} under a model \mathcal{M} is thus mapped by a GT to the energy of a new state \boldsymbol{s}^{\prime}=\boldsymbol{b}(\boldsymbol{s}) of a new spin model \mathcal{M}^{\prime} : \displaystyle H(\boldsymbol{s}\mid\boldsymbol{g},\,\mathcal{M}) \displaystyle=\sum_{\boldsymbol{\mu}^{\prime}\in\mathcal{M}^{\prime}}g_{\boldsymbol{\mu}^{\prime}}\,\phi^{\boldsymbol{\mu}^{\prime}}(\boldsymbol{s}^{\prime})=H(\boldsymbol{s}^{\prime}\mid\boldsymbol{g}^{\prime},\,\mathcal{M}^{\prime})\,, (A58) where \mathcal{M}^{\prime}=\mathcal{T}_{b}[\mathcal{M}]=\{\boldsymbol{\mu}^{\prime}=\boldsymbol{T}^{-1}\boldsymbol{\mu}\mid\boldsymbol{\mu}\in\mathcal{M}\} , and \boldsymbol{g}^{\prime}=\mathcal{T}_{b}[\boldsymbol{g}] is a permutation of the parameters in \boldsymbol{g} that is such that g_{\boldsymbol{\mu}^{\prime}}=g_{\boldsymbol{\mu}} for \boldsymbol{\mu}^{\prime}=\boldsymbol{T}^{-1}\boldsymbol{\mu} . Proof: models related by GTs have the same partition function (for Sec. 4.6 ). Consider a q -state spin model \mathcal{M}=\{\phi^{\boldsymbol{\mu}_{1}},\dots,\phi^{\boldsymbol{\mu}_{K}}\} and a GT of this model, \mathcal{M}^{\prime}=\mathcal{T}_{\boldsymbol{b}}[\mathcal{M}]=\{\phi^{\boldsymbol{\mu}^{\prime}_{1}},\dots,\phi^{\boldsymbol{\mu}^{\prime}_{K}}\} , with \phi^{\boldsymbol{\mu}^{\prime}_{k}}=\mathcal{T}_{\boldsymbol{b}}[\phi^{\boldsymbol{\mu}_{k}}] for all k\in[1,K] . We labeled the operators in the same order in both models such that the k -th parameter of \mathcal{M}^{\prime} is equal to the k -th parameter of \mathcal{M} : g_{\boldsymbol{\mu}^{\prime}_{k}}=g_{\boldsymbol{\mu}_{k}} , where \boldsymbol{\mu}_{k}^{\prime}=T_{\boldsymbol{b}}^{-1}\boldsymbol{\mu}_{k} are related by the GT. The partition function of \mathcal{M}^{\prime} is given by: \displaystyle Z_{\mathcal{M}^{\prime}}(\boldsymbol{g}^{\prime})=\sum_{\boldsymbol{s}^{\prime}\in\Omega}\exp\left({\;\displaystyle\sum_{k=1}^{K}g_{\boldsymbol{\mu}_{k}^{\prime}}\phi^{\boldsymbol{\mu}_{k}^{\prime}}(\boldsymbol{s}^{\prime})}\right)\,, (A59) where \Omega denotes the set of all possible q^{n} spin states and \boldsymbol{g}^{\prime}=(g_{\boldsymbol{\mu}^{\prime}_{1}},\dots,g_{\boldsymbol{\mu}^{\prime}_{K}}) is the vector of parameters of \mathcal{M}^{\prime} . The gauge transformation \mathcal{T}_{\boldsymbol{b}} corresponds to the change of spin basis \boldsymbol{s}^{\prime}=\boldsymbol{b}(\boldsymbol{s}) . The gauge transform operators are then related to the original operators by \phi^{\boldsymbol{\mu}^{\prime}}(\boldsymbol{s}^{\prime})=\mathcal{T}_{\boldsymbol{b}}[\phi^{\boldsymbol{\mu}}](\boldsymbol{s}^{\prime})=\phi^{\boldsymbol{\mu}}[\boldsymbol{b}^{-1}(\boldsymbol{s}^{\prime})] (see Def. 18 ), which gives: \displaystyle Z_{\mathcal{M}^{\prime}}(\boldsymbol{g}^{\prime})=\sum_{\boldsymbol{s}^{\prime}\in\Omega}\exp\left({\;\displaystyle\sum_{k=1}^{K}g_{\boldsymbol{\mu}_{k}^{\prime}}\phi^{\boldsymbol{\mu}_{k}}[\boldsymbol{b}^{-1}(\boldsymbol{s}^{\prime})]}\right)\,. (A60) We use the fact that a GT is an automorphism of the state space \Omega (bijection between states in \Omega ) to perform the change of variable \boldsymbol{s}=\boldsymbol{b}^{-1}(\boldsymbol{s}^{\prime}) in the first sum and re-write it as: \displaystyle Z_{\mathcal{M}^{\prime}}(\boldsymbol{g}^{\prime})=\sum_{\boldsymbol{s}\in\Omega}\exp\left({\;\displaystyle\sum_{k=1}^{K}g_{\boldsymbol{\mu}_{k}^{\prime}}\phi^{\boldsymbol{\mu}_{k}}(\boldsymbol{s})}\right)=\sum_{\boldsymbol{s}\in\Omega}\exp\left({\;\displaystyle\sum_{k=1}^{K}g_{\boldsymbol{\mu}_{k}}\phi^{\boldsymbol{\mu}_{k}}(\boldsymbol{s})}\right)=Z_{\mathcal{M}}(\boldsymbol{g})\,. (A61) Here, in the second equality, we used that k -th parameter of \mathcal{M} is equal to the k -th parameter of \mathcal{M}^{\prime} , g_{\boldsymbol{\mu}^{\prime}_{k}}=g_{\boldsymbol{\mu}_{k}} , following the labeling choice made above. ∎ C.3 Real-valued spin models and reduced model Proof of Property . Consider two c.c. operators (\boldsymbol{\mu},-\boldsymbol{\mu})\in[(\mathbb{Z}/q\mathbb{Z})^{n}]^{2} . We recall that the notation -\boldsymbol{\mu} was defined in Sec 2.1 as -\boldsymbol{\mu}=(q-\mu_{1},\dots,q-\mu_{n}) . Consider a gauge transformation \mathcal{T} of these operators with matrix representation \boldsymbol{T} . We denoted by t_{ij} the elements of the inverse matrix \boldsymbol{T}^{-1} . We then have that: \displaystyle\mathcal{T}[-\boldsymbol{\mu}]=\boldsymbol{T}^{-1}(-\boldsymbol{\mu})=\bigg(\Big(\sum_{j=1}^{n}t_{ij}\,(q-\mu_{j})\Big){\rm mod}\,q\bigg)_{i}=-\boldsymbol{T}^{-1}\boldsymbol{\mu}=-\mathcal{T}[\boldsymbol{\mu}]\,, where were we used that (\sum_{j=1}^{n}t_{ij}\,(q-\mu_{j}))({\rm mod}\,q)=-(\sum_{j=1}^{n}t_{ij}\,\mu_{j})({\rm mod}\,q) . ∎ For the two proofs below, we used the decomposition of Definition 10 for both the spin model \mathcal{M} and its transformed model \mathcal{M}^{\prime}=\mathcal{T}[\mathcal{M}] under a GT \mathcal{T} , i.e. we decompose the models as \mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} and \mathcal{M}^{\prime}=\mathcal{M}_{0}^{\prime}\cup\mathcal{M}_{1}^{\prime}\cup\mathcal{M}_{1}^{\prime*} . We show that \mathcal{T}[\mathcal{M}_{0}]=\mathcal{M}_{0}^{\prime} and that \mathcal{T}[\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*}]=\mathcal{M}_{1}^{\prime}\cup\mathcal{M}_{1}^{\prime*} . Proof that: for all \boldsymbol{\mu}\in\mathcal{M}_{0} , \mathcal{T}[\boldsymbol{\mu}]\in\mathcal{M}_{0}^{\prime} . For all \boldsymbol{\mu}\in\mathcal{M}_{0} , -\boldsymbol{\mu}=\boldsymbol{\mu} . This implies that \mathcal{T}[-\boldsymbol{\mu}]=\mathcal{T}[\boldsymbol{\mu}]=\boldsymbol{\mu}^{\prime} . Using that under a GT \mathcal{T}[-\boldsymbol{\mu}]=-\mathcal{T}[\boldsymbol{\mu}]=-\boldsymbol{\mu}^{\prime} (see Property ), one gets that the operator \boldsymbol{\mu}^{\prime} verifies \boldsymbol{\mu}^{\prime}=-\boldsymbol{\mu}^{\prime} , and thus is an element of \mathcal{M}_{0}^{\prime} . ∎ Proof by contradiction that: for all \boldsymbol{\mu}_{1}\in\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} , \mathcal{T}[\boldsymbol{\mu}_{1}]\in\mathcal{M}_{1}^{\prime}\cup\mathcal{M}_{1}^{\prime*} . Take an operator \boldsymbol{\mu}\in\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} , by definition -\boldsymbol{\mu}\neq\boldsymbol{\mu} in (\mathbb{Z}/q\mathbb{Z})^{n} . Suppose that its transformation \boldsymbol{\mu}^{\prime}=\mathcal{T}[\boldsymbol{\mu}] is an element of \mathcal{M}_{0}^{\prime} . By definition of \mathcal{M}_{0}^{\prime} , the operator then verifies that -\boldsymbol{\mu}^{\prime}=\boldsymbol{\mu}^{\prime} in (\mathbb{Z}/q\mathbb{Z})^{n} . Using the inverse GT on both side of this equality we get that: \mathcal{T}^{-1}[-\boldsymbol{\mu}^{\prime}]=\mathcal{T}^{-1}[\boldsymbol{\mu}^{\prime}] , where \mathcal{T}^{-1}[\boldsymbol{\mu}^{\prime}]=\boldsymbol{\mu} and \mathcal{T}^{-1}[-\boldsymbol{\mu}^{\prime}]=-\mathcal{T}^{-1}[\boldsymbol{\mu}^{\prime}] as \mathcal{T}^{-1} is a GT (see Property ). We finally get that -\boldsymbol{\mu}=\boldsymbol{\mu} , which is in contradiction with the fact that \boldsymbol{\mu}\in\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} . This means that \boldsymbol{\mu}^{\prime}=\mathcal{T}[\boldsymbol{\mu}] is not an element of \mathcal{M}_{0}^{\prime} , and is therefore in \mathcal{M}_{1}^{\prime}\cup\mathcal{M}_{1}^{\prime*} . ∎ Proof of the reduced loop structure. Consider a real-valued spin model \mathcal{M} that can be written under the form \mathcal{M}=\mathcal{M}_{1}\cup\mathcal{M}_{1}^{*} with the decomposition of Definition 10 (i.e., for which \mathcal{M}_{0}=\emptyset ). This is always the case for a real-valued models with q prime and q>2 (for which all the operators are included by c.c. pairs and verify that -\boldsymbol{\mu}\neq\boldsymbol{\mu} ). The reduced set of loops of \mathcal{M} , excluding trivial loops due to c.c. operators, are given by Eq. ( 68 ): \displaystyle\mathcal{L}^{cc}_{q}(\mathcal{M})=\bigg\{\boldsymbol{\ell}\in(\mathbb{Z}/q\mathbb{Z})^{K_{1}}\;\Big|\;\sum_{j=1}^{K_{1}}\ell_{j}\,\boldsymbol{\mu}_{j}=\boldsymbol{0}\bigg\}\;, (A62) where K_{1}=|\mathcal{M}_{1}| is the number of operators in \mathcal{M}_{1} . Using the reduced matrix representation \boldsymbol{M}_{1}=(\boldsymbol{\mu}_{1},\dots,\boldsymbol{\mu}_{K_{1}}) of \mathcal{M}_{1} and viewing \boldsymbol{\ell} as a column vector, we can rewrite \mathcal{L}^{cc}_{q}(\mathcal{M}) as follows: \displaystyle\mathcal{L}^{cc}_{q}(\mathcal{M})=\bigg\{\boldsymbol{\ell}\in(\mathbb{Z}/q\mathbb{Z})^{K_{1}}\;\Big|\;\boldsymbol{M}_{1}\boldsymbol{\ell}=\boldsymbol{0}\bigg\}=\ker(\boldsymbol{M}_{1})\;. (A63) One could have also directly identified in Eq. ( A62 ) that \mathcal{L}^{cc}_{q}(\mathcal{M})=\mathcal{L}_{q}(\mathcal{M}_{1}) , which gives the same result. ∎ Appendix D Properties of MCMs The proofs in this section are almost identical to the one derived for the binary case in Ref. 9 (Supplementary Materials) and Ref. 15 , just generalized to the case q>2 . D.1 Matrix representations of the MCMs and GTs in Figure 9 For the models in Fig. 9 .a, we have that q=3 , which means that the matrix representations and operations are over \mathbb{Z}/3\mathbb{Z} . The matrix representations of \mathcal{M}_{1} and \mathcal{M}_{1}^{\prime} are respectively: Werecallthatthefullmodelisobtainedbycombiningtheoperatorsof M _1 withtheirc.c.,i.e. M = M _1∪ M _1^* (idemfor M ’ ).Themodels M and M ’ aretwoMCMsthatbelongtothesameequivalenceclass;theyeachhavetwoICCsofrespectiverank 2 and 1 .Inthematricesabove,weindicatedwithdifferentcolorstheoperatorsthatbelongtothetwoICCs.WehighlightedthefactthatthesecondMCMappearsinapreferredbasisbycoloringonlytheentriesof M _1’ correspondingtothesubsetofbasisvariables σ _i overwhichtheICCisbased,highlightingtheblockdiagonalformofthematrix.Forthegaugetransformation,weusedthesameGTandinverseGTasinFig.~\ref{fig:GT_and_Loops}.a,whicharerepresentedrespectivelybythematrices T and T ^-1 inEq.~\eqref{eq:exFig:GT:T}.Onecaneasilycheckthat M _1’= T ^-1 M _1 in Z /3 Z .\par ForthemodelsinFig.~\ref{fig:MCM:examples}.b,wehavethat q=4 ,whichmeansthatthematrixrepresentationsandoperationsareover Z /4 Z .Thematrixrepresentationsofthemodels M and M ’ arerespectively:\begin{aligned} \boldsymbol{M}=\begin{pNiceArray}\qquad{\rm and}\qquad\boldsymbol{M}^{\prime}=\begin{pNiceArray}\;\;.\end{aligned}Themodels M and M ’ aretwoMCMsthatarebelongtothesameequivalenceclass;theyeachhaveasingleICCofrank 1 .Onecanseeinthematrix M ’ abovethatthemodel M ’ isinapreferredbasis,asitsoperatorsareallbasedonasinglevariable(alltheentriesbasedon σ _2 arezeros).ThematrixrepresentationsoftheGT T andinverseGT T ^-1 arerespectively:\begin{aligned} \qquad\boldsymbol{T}=\begin{array}[]{ccc}\sigma_{1}&\sigma_{2}&\\ 1&1&s_{1}\\ 1&0&s_{2}\\ \end{array}\qquad\Leftrightarrow\qquad\boldsymbol{T}^{-1}=\begin{array}[]{ccc}s_{1}&s_{2}&\\ 0&1&\sigma_{1}\\ 1&3&\sigma_{2}\\ \end{array}\;\;.\end{aligned}Onecaneasilycheckthat TT ^-1= I _2 over Z /4 Z ,andthat M ’= T ^-1 M orequivalentlythat M = TM ’ .Formally,thematricesshouldbereadintermsofthecolorvariables α _i and α _i’ ,insteadofthespinvariables(seeSec.~\ref{Sec:GT:MatrixRepresentation}).Forexample,theGT~ T inFig.~\ref{fig:MCM:examples}.bisequivalentlywrittenintermsofthecolorvariablesas α _1’= α _1+ α _2 and α _2’= α _1 .Thematrix T inEq.~\eqref{app:eq:exFig:GT:T}isthematrixrepresentationofthislineartransformation.\par\par D.2 GTs of MCMs D.3 Number of MCMs in a class of MCMs We give the main lines of the proof of the results in Lemma 38 . Consider a system with n q -state spin variables. Let us denote \mathcal{N}_{q}(n,r) the number of different ways to choose r independent operators in this n -spin system. For the special case r=n , this number corresponds to the number of possible gauge transformations in the n spin system, \mathcal{N}_{q}(n,r)=|\mathcal{G}_{q}(n)| , given in Eq. ( 92 ) and ( 93 ). Using the same approach as the one used to compute |\mathcal{G}_{q}(n)| , we obtain more generally for any r\in\{1,\dots,n\} that: \displaystyle\textrm{for}\;q\;\textrm{prime},\;\qquad \displaystyle\mathcal{N}_{q}(n,r)=\prod_{i=0}^{r-1}(q^{n}-q^{i})\,; (A64) \displaystyle\textrm{for}\;q\;\textrm{not prime},\;\qquad \displaystyle\mathcal{N}_{q}(n,r)=\prod_{k=1}^{K}p_{k}^{\,(m_{k}-1)n^{2}}\,\prod_{i=0}^{r-1}(p_{k}^{\,n}-p_{k}^{\,i})\,. (A65) From this result, we can compute the number of (strongly) independent models with rank r , among all real-valued spin models of n spins. This number is given by: \displaystyle\mathcal{N}_{ind}(n,r)=\begin{cases}&\displaystyle\frac{\mathcal{N}_{q}(n,r)}{r!}\,,\qquad{\rm for}\;q=2\,,\\[5.0pt] &\displaystyle\frac{\mathcal{N}_{q}(n,r)}{2^{r}\,r!}\,,\qquad{\rm for}\;q>2\,.\end{cases} (A66) This corresponds to the number of ways of choosing r independent operators in the set of all possible q^{n}-1 operators, divided by the number of possible permutations of these r elements. For q>2 , the division by 2^{r} accounts for the fact that using an operator or its c.c. in the independent set defines the same independent model (because real-valued models contain both conjugate operators, and because, for q>2 , operators that can be used in an independent set cannot be their own conjugate). Take an MCM \mathcal{M} with a single complete component of rank r . The number of different MCMs in the same class as \mathcal{M} (i.e., with a single C.C. of rank r ) is given by the total number of possible GTs of \mathcal{M} , divided by the number of these GTs that leaves \mathcal{M} invariant. This is equal to the number of ways to choose r independent (basis) operators among all possible (q^{n}-1) operators, divided by the number of ways to choose r independent (basis) operators among the (q^{r}-1) operators that are already in the \mathcal{M} , which is: \displaystyle\mathcal{N}_{\rm CC}(n,r)=\displaystyle\frac{\mathcal{N}_{q}(n,r)}{\mathcal{N}_{q}(r,r)}=\begin{cases}\;\;\displaystyle\prod_{i=0}^{r-1}\,\frac{q^{n}-q^{i}}{q^{r}-q^{i}}\,,&\qquad{\rm for}\;q\;{\rm prime},\\[4.0pt] \;\;\displaystyle\prod_{k=1}^{K}p_{k}^{(m_{k}-1)(n^{2}-r^{2})}\prod_{i=0}^{r-1}\frac{p_{k}^{n}-p_{k}^{i}}{p_{k}^{r}-p_{k}^{i}}\,,&\qquad{\rm for}\;q\;\textrm{not prime}.\end{cases} (A67) Finally, take an MCM \mathcal{M} with m ICCs and denote by m_{r_{a}} the number of ICCs of rank r_{a} in \mathcal{M} . The number of different MCMs in the same class as \mathcal{M} (i.e., with the same sequence of multiplicity \{m_{r_{a}}\}_{1\leq r_{a}\leq n} of their ICCs) can be obtained by combining the two previous arguments: \displaystyle\mathcal{N}_{\rm MCM}(n,\{m_{r_{a}}\}_{1\leq r_{a}\leq n})=\displaystyle\frac{\mathcal{N}_{q}(n,r)}{\displaystyle\prod_{r_{a}=1}^{n}(m_{r_{a}}!)\;\,\mathcal{N}_{q}(r_{a},r_{a})^{m_{r_{a}}}}\;, (A68) where the factors 1/m_{r_{a}}! account for permutations among ICCs of the same size. D.4 Notations for the proofs in the sections below Throughout the paper, we consider a system of n discrete random variables \alpha_{i} that can take integer values between 0 and (q-1) with q\geq 2 . A state of the system is denoted \boldsymbol{\alpha}=(\alpha_{1},\cdots,\alpha_{n})\in(\mathbb{Z}/q\mathbb{Z})^{n} , and a dataset is composed of N observations of the system and is denoted \boldsymbol{\hat{\alpha}}=(\boldsymbol{\alpha}^{(1)},\cdots,\,\boldsymbol{\alpha}^{(N)}) . We assume the system to be stationary and that the observed states are randomly sampled from the same underlying distribution, p(\boldsymbol{\alpha}\,|\,\boldsymbol{g},\mathcal{M}) , defined by a parametric model \mathcal{M} . In the following, we consider that \mathcal{M} is an MCM with a single Independent Complete Component (ICC) \mathcal{M}_{a} of rank r_{a} (with r_{a}\leq n ). For the sake of simplicity of the derivations, we consider that \mathcal{M} is already written in a preferred basis and we reduce the system to the r_{a} variables modeled by \mathcal{M}_{a} . This corresponds to reducing the space to the basis variables \boldsymbol{\alpha}_{a} on which the ICC \mathcal{M}_{a} is based, and considering the model distribution p_{a}(\boldsymbol{\alpha}_{a}\,|\,\boldsymbol{g}_{a},\mathcal{M}_{a}) , which is a distribution over r_{a} variables only (instead of n ). To simplify the notation, we then drop the index “ a ” used to label the ICCs. We denote the model \mathcal{M}_{icc} and its rank r , and use the notation \boldsymbol{\alpha}=(\alpha_{1},\cdots,\alpha_{r})\in(\mathbb{Z}/q\mathbb{Z})^{r} for the state of the system reduced to the r variables (strictly speaking, these variables can be any subset of the variables \boldsymbol{\alpha} introduced in the previous paragraph). D.5 Alternative parametrization of an Independent Complete Components (ICC). The ICC \mathcal{M}_{icc} is a complete model (see Sec. ( 2 )) for the sub-system of r=\rank(\M_{icc}) variables. The model has (q^{r}-1) parameters \boldsymbol{g} and can be (equivalently) defined as the following parametric family of probability distributions: \displaystyle p(\boldsymbol{\alpha}\,|\,\boldsymbol{\eta},\mathcal{M}_{icc})=\sum_{\boldsymbol{\mu}\in(\mathbb{Z}/q\mathbb{Z})^{r}}\,\eta_{\boldsymbol{\mu}}\,\delta(\boldsymbol{\alpha}-\boldsymbol{\mu})\,, (A69) where each \eta_{\boldsymbol{\mu}} is the probability that the system is in the state \boldsymbol{\alpha}=\boldsymbol{\mu} , here considered as a parameter. We denote \boldsymbol{\eta} the vector of the (q^{r}-1) parameters \eta_{\boldsymbol{\mu}} for all non-zero \boldsymbol{\mu} . The remaining probability \eta_{\boldsymbol{0}}=p(\boldsymbol{0}) is defined by the normalization: \displaystyle\eta_{\boldsymbol{0}}=1-\sum_{\boldsymbol{\mu}=1}^{q^{r}-1}\eta_{\boldsymbol{\mu}}\,. (A70) In this equation, the sum is over all the non-zero vectors \boldsymbol{\mu}\in[(\mathbb{Z}/q\mathbb{Z})^{r}]^{*} . We denoted each vector \boldsymbol{\mu} by its integer value in base q , which allows ordering the vectors \boldsymbol{\mu} from 1 to (q^{r}-1) . For instance, the vector \boldsymbol{\mu}=1 has its first entry equal to 1 , and all the other entries are equal to 0 . The vector \boldsymbol{\mu}=(q^{r}-1) has all its r entries equal to (q-1) . Substituting the expression of \eta_{\boldsymbol{0}} in Eq. ( A69 ), we get: \displaystyle p(\boldsymbol{\alpha}\,|\,\boldsymbol{\eta},\mathcal{M}_{icc})=\sum_{\boldsymbol{\mu}=1}^{q^{r}-1}\,\eta_{\boldsymbol{\mu}}\,\delta(\boldsymbol{\alpha}-\boldsymbol{\mu})+\left(1-\sum_{\boldsymbol{\mu}=1}^{q^{r}-1}\eta_{\boldsymbol{\mu}}\right)\,\delta(\boldsymbol{\alpha}-\boldsymbol{0})\,, (A71) where \boldsymbol{\mu}=\boldsymbol{0} is the state where all the variables have the value 0 . D.6 Fisher Information Matrix (FIM) for an ICC. For an MCM (with multiple ICCs), the Fisher Information Matrix (FIM) in Eq. ( 109 ) is block diagonal, where each block corresponds to the FIM restricted to a single ICC. This is because the model probability distribution of an MCM factorizes over its ICCs, which also have non-overlapping sets of parameters. Consequently, the determinant of the FIM of an MCM is the product of the determinant of the FIM for each ICC, i.e., for an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} with parameters \boldsymbol{g}=\cup_{a\in\mathcal{A}}\boldsymbol{g}_{a} : \displaystyle\det\mathcal{I}(\boldsymbol{g})=\prod_{a\in\mathcal{A}}\det\mathcal{I}_{a}(\boldsymbol{g}_{a})\,. (A72) Let us now compute the FIM \mathcal{I}_{a} for a single ICC. For simplicity, we consider a system reduced to a single ICC with the notations specified in Sec. D.4 (in particular, we drop the index “ a ” used to label ICCs). For the ICC probability distribution with the new parametrization in Eq. ( A71 ), the Fisher Information Matrix (FIM) is the square matrix of order (q^{r}-1) with elements: \displaystyle\mathcal{I}_{\boldsymbol{\mu}\boldsymbol{\nu}}(\boldsymbol{\eta}) \displaystyle=-\left\langle\partial_{\eta_{\boldsymbol{\mu}}}\partial_{\eta_{\boldsymbol{\nu}}}\log p(\boldsymbol{\alpha}\,|\,\boldsymbol{\eta},\mathcal{M}_{icc})\right\rangle\,,\qquad\forall\,\boldsymbol{\mu},\boldsymbol{\nu}\in[(\mathbb{Z}/q\mathbb{Z})^{r}]^{*}\,, (A73) where the average is taken over the model distribution P(\boldsymbol{\alpha}\,|\,\mathcal{M}_{icc},\,\boldsymbol{\eta}) . Substituting Eq. ( A71 ) and taking the two derivatives gives, \forall\,\boldsymbol{\mu},\boldsymbol{\nu}\in[(\mathbb{Z}/q\mathbb{Z})^{r}]^{*} : \displaystyle\mathcal{I}_{\boldsymbol{\mu}\boldsymbol{\nu}}(\boldsymbol{\eta}) \displaystyle=\left\langle\frac{(\delta(\boldsymbol{\alpha}-\boldsymbol{\mu})-\delta(\boldsymbol{\alpha}-\boldsymbol{0}))(\delta(\boldsymbol{\alpha}-\boldsymbol{\nu})-\delta(\boldsymbol{\alpha}-\boldsymbol{0}))}{\left[P(\boldsymbol{\alpha}\,|\,\mathcal{M}_{icc},\,\boldsymbol{\eta})\right]^{2}}\right\rangle (A74) \displaystyle=\sum_{\boldsymbol{\alpha}\in(\mathbb{Z}/q\mathbb{Z})^{r}}\,\frac{\delta(\boldsymbol{\alpha}-\boldsymbol{\mu})\delta(\boldsymbol{\alpha}-\boldsymbol{\nu})+\delta(\boldsymbol{\alpha}-\boldsymbol{0})}{P(\boldsymbol{\alpha}\,|\,\mathcal{M}_{icc},\,\boldsymbol{\eta})} (A75) \displaystyle\mathcal{I}_{\boldsymbol{\mu}\boldsymbol{\nu}}(\boldsymbol{\eta}) \displaystyle=\frac{\delta_{\boldsymbol{\mu},\boldsymbol{\nu}}}{\eta_{\boldsymbol{\mu}}}+\frac{1}{\eta_{\boldsymbol{0}}}\,, (A76) in which \eta_{\boldsymbol{0}} is given by Eq. ( A70 ). We recall that \boldsymbol{\eta} is a vector of the (q^{r}-1) parameters \eta_{\boldsymbol{\mu}} for all \boldsymbol{\mu}\in[(\mathbb{Z}/q\mathbb{Z})^{r}]^{*} . For the following sections, it is useful to compute the determinant of \mathcal{I} . To do so, we observe that \mathcal{I} can be written under the form \mathcal{I}=\mathbf{D}+\mathbf{u}\mathbf{v}^{\top} , where \mathbf{D} is a diagonal matrix with entries \mathbf{D}_{\boldsymbol{\mu}\boldsymbol{\mu}}=1/\eta_{\boldsymbol{\mu}} for \forall\,\boldsymbol{\mu}\in[(\mathbb{Z}/q\mathbb{Z})^{r}]^{*} , and where \mathbf{u} and \mathbf{v} are two (q^{r}-1) -dimensional column vectors with, respectively, all entries equal to 1 and all entries equal to 1/\eta_{0} . The matrix determinant lemma then allows to compute the determinant of the FIM: \displaystyle\det\mathcal{I}(\boldsymbol{\eta}) \displaystyle=(1+\mathbf{v}^{\top}\mathbf{D}^{-1}\mathbf{u})\,\det\mathbf{D}=\left(1+\frac{1}{\eta_{\boldsymbol{0}}}\sum_{\boldsymbol{\mu}=1}^{q^{r}-1}\eta_{\boldsymbol{\mu}}\right)\,\prod_{\boldsymbol{\mu}=1}^{q^{r}-1}\frac{1}{\eta_{\boldsymbol{\mu}}} (A77) \displaystyle\det\mathcal{I}(\boldsymbol{\eta}) \displaystyle=\prod_{\boldsymbol{\mu}=0}^{q^{r}-1}\;\frac{1}{\eta_{\boldsymbol{\mu}}}\,, (A78) in which \eta_{\boldsymbol{0}} is given by Eq. ( A70 ). D.7 Geometric complexity of an ICC. Assuming Jeffreys’ prior over the model parameters, the geometric complexity of a spin model is given by 9 : \displaystyle c_{\mathcal{M}}=\log\int\sqrt{\det\mathcal{I}(\boldsymbol{g})}\,d\boldsymbol{g}\,, (A79) where the integral is over all possible values of the parameters. Using the factorization of \det\mathcal{I}(\boldsymbol{g}) in Eq. ( A72 ), the geometric complexity of an MCM can be written as the sum of the geometric complexity of its ICCs, as in Eq. ( 134 ). In the following, we compute the complexity of a single ICC of rank r , which we denote c_{icc}(r) . For simplicity, we consider a system reduced to a single ICC with the notations specified in Sec. D.4 . Proof of the geometric complexity of an ICC in Eq. ( 135 ). The geometric part of the MDL complexity 43 ; 45 is defined as c_{icc}(r)=\log V_{icc}(r) , where V_{icc}(r) is the volume of the K=(q^{r}-1) -dimensional model manifold: \displaystyle V_{icc}(r)=\int_{[0,1]^{K}}\sqrt{\det\mathcal{I}(\boldsymbol{\eta})}\,d\boldsymbol{\eta}\,. (A80) Substituting Eq. ( A78 ), one gets: \displaystyle V_{icc}(r)=\int_{[0,1]^{K}}\eta_{\boldsymbol{0}}^{-1/2}\,\prod_{\boldsymbol{\mu}=1}^{q^{r}-1}\eta_{\boldsymbol{\mu}}^{-1/2}\,d\boldsymbol{\eta}\,,\qquad{\rm in\;which}\;\;\eta_{\boldsymbol{0}}=1-\sum_{\boldsymbol{\mu}=1}^{q^{r}-1}\eta_{\boldsymbol{\mu}}\,. (A81) Here one can recognize the multivariate beta function: \displaystyle V_{icc}(r) \displaystyle=B\underset{q^{r}\;{\rm terms}}{\underbrace{\left(\frac{1}{2},\,\cdots,\,\frac{1}{2}\right)}}=\frac{\displaystyle\prod_{i=0}^{K}\,\Gamma\left(\frac{1}{2}\right)}{\displaystyle\Gamma\left(\sum_{i=0}^{K}\frac{1}{2}\right)}=\frac{\displaystyle\pi^{\frac{q^{r}}{2}}}{\displaystyle\Gamma\left(\frac{q^{r}}{2}\right)}\,, (A82) which gives the complexity term: \displaystyle c_{icc}(r)=\frac{q^{r}}{2}\log\pi-\log\Gamma\left(\frac{q^{r}}{2}\right)\,. (A83) ∎ For q=2 , one recovers the result obtained in the binary case by Ref. 9 : \displaystyle c_{icc}(r)=2^{r-1}\log\pi-\log\Gamma(2^{r-1})\,. (A84) D.8 Likelihood function for an ICC. Using the definition of the ICC in Eq. ( A69 ), we compute the likelihood of the ICC for the dataset \boldsymbol{\hat{\alpha}} : \displaystyle P(\boldsymbol{\hat{\alpha}}\,|\,\boldsymbol{\eta},\mathcal{M}_{icc}) \displaystyle=\prod_{i=1}^{N}p(\boldsymbol{\alpha}^{(i)}\,|\,\boldsymbol{\eta},\mathcal{M}_{icc}) (A85) \displaystyle=\prod_{\boldsymbol{\mu}=0}^{q^{r}-1}\;\eta_{\boldsymbol{\mu}}^{\;k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}})} (A86) in which \eta_{0} satisfies Eq. ( A70 ) and where k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}}) is the number of times the state \boldsymbol{\alpha}=\boldsymbol{\mu} occurs in the dataset \boldsymbol{\hat{\alpha}} . D.9 Jeffreys’ prior. Jeffreys’ prior for a parametric model with parameters \boldsymbol{g} is defined as 26 : \displaystyle P_{0}(\boldsymbol{g})\propto\sqrt{\det\mathcal{I}(\boldsymbol{g})}\,, (A87) where \mathcal{I}(\boldsymbol{g}) is the FIM [of the model]. Using the factorization of \det\mathcal{I}(\boldsymbol{g}) in Eq. ( A72 ), Jeffreys’ prior for an MCM factorizes over its ICCs: P_{0}(\boldsymbol{g})=\prod_{a\in\mathcal{A}}P_{0}(\boldsymbol{g}_{a}) , for an MCM \mathcal{M}=\cup_{a\in\mathcal{A}}\mathcal{M}_{a} with parameters \boldsymbol{g}=\cup_{a\in\mathcal{A}}\boldsymbol{g}_{a} . The factorization of the prior over the parameters is used for the factorization of the model evidence in Eq. ( 132 ). In the following, we obtain a closed-form expression for Jeffreys’ prior for a single ICC. For simplicity, we consider a system reduced to a single ICC with the notations specified in Sec. D.4 . For the ICC distributions ( A69 ) parametrized by \boldsymbol{\eta} , Jeffreys’ Prior is computed as: \displaystyle P_{0}(\boldsymbol{\eta})=\frac{1}{V_{icc}}\,\sqrt{\det\mathcal{I}(\boldsymbol{\eta})}\,, (A88) where \mathcal{I}(\boldsymbol{\eta}) is the FIM and the normalization V_{icc} is the volume in Eq. ( A81 ). Substituting the expression of \det\mathcal{I}(\boldsymbol{\eta}) from Eq. ( A78 ), one gets: \displaystyle P_{0}(\boldsymbol{\eta})=\frac{1}{V_{icc}}\,\prod_{\boldsymbol{\mu}=0}^{q^{r}-1}\,\eta_{\boldsymbol{\mu}}^{-1/2}\,,\qquad{\rm in\;which}\;\;\eta_{\boldsymbol{0}}=1-\sum_{\boldsymbol{\mu}=1}^{q^{r}-1}\eta_{\boldsymbol{\mu}}\,. (A89) Here, one can recognize the symmetric Dirichlet distribution with hyperparameter 1/2 . D.10 Evidence of an ICC. Proof of Eq. ( 133 ). Combining the expressions in Eq. ( A86 ) for the likelihood function and in Eq. ( A89 ) for Jeffreys’ prior P_{0}(\boldsymbol{\eta}) , the evidence (or marginal likelihood) of the ICC is finally given by: \displaystyle P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}_{icc}) \displaystyle=\int_{[0,1]^{K}}P(\boldsymbol{\hat{\alpha}}\,|\,\boldsymbol{\eta},\mathcal{M}_{icc})\,P_{0}(\boldsymbol{\eta})\,d\boldsymbol{\eta} (A90) \displaystyle=\frac{1}{V_{icc}}\,\int_{[0,1]^{K}}\,\prod_{\boldsymbol{\mu}=0}^{q^{r}-1}\eta_{\boldsymbol{\mu}}^{\,k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}})}\,\eta_{\boldsymbol{\mu}}^{-1/2}\,d\eta_{\boldsymbol{\mu}}\,. (A91) where K=(q^{r}-1) is the number of parameters in the ICC. Here we recognize the (multivariate) Beta function of the q^{r} variables (k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}})+1/2) : \displaystyle P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}_{icc})\;=\;\frac{\displaystyle B\left(k_{0}+\frac{1}{2},\,\cdots,\,k_{q^{r}-1}+\frac{1}{2}\right)}{\displaystyle B\left(\frac{1}{2},\,\cdots,\,\frac{1}{2}\right)}\;=\;\frac{\displaystyle\Gamma\left(\frac{q^{r}}{2}\right)}{\displaystyle\pi^{\frac{q^{r}}{2}}}\;\frac{\displaystyle\prod_{\boldsymbol{\mu}=0}^{q^{r}-1}\,\Gamma\left(k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}})+\frac{1}{2}\right)}{\displaystyle\Gamma\left(N+\frac{q^{r}}{2}\right)}\;, (A92) where k_{\boldsymbol{\mu}} is the number of times that the state \boldsymbol{\mu} occurs in the dataset \boldsymbol{\hat{\alpha}} . For q=2 , we recover the results obtained for the binary case in Ref. 15 . Rearranging the terms: \displaystyle P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}_{icc})\;=\;\frac{\displaystyle\Gamma\left(\frac{q^{r}}{2}\right)}{\displaystyle\Gamma\left(N+\frac{q^{r}}{2}\right)}\;\prod_{\boldsymbol{\mu}=0}^{q^{r}-1}\left[\frac{\displaystyle\,\Gamma\left(k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}})+\frac{1}{2}\right)}{\displaystyle\sqrt{\pi}}\right]\;, (A93) and one can observe that, for all the states \boldsymbol{\mu} that don’t occur in the dataset ( k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}})=0 ), one has \Gamma(k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}})+1/2)/\sqrt{\pi}=1 , and therefore the evidence can be re-written as: \displaystyle P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}_{icc})\;=\;\frac{\displaystyle\Gamma\left(\frac{q^{r}}{2}\right)}{\displaystyle\Gamma\left(N+\frac{q^{r}}{2}\right)}\;\prod_{\boldsymbol{\mu}\in\boldsymbol{\hat{\alpha}}}\left[\frac{\displaystyle\,\Gamma\left(k_{\boldsymbol{\mu}}(\boldsymbol{\hat{\alpha}})+\frac{1}{2}\right)}{\displaystyle\sqrt{\pi}}\right]\;, (A94) where the product is now only over the states observed in the dataset \boldsymbol{\hat{\alpha}} . ∎ D.11 Expansion of the log-evidence for large N and MDL principle. Bayesian model selection and Minimum Description length principle are already known to be equivalent for large dataset, assuming Jeffreys’ prior over the parameters. For completeness, we re-derive this result in the particular case of MCM. Let us focus on the evidence of the complete model, as the extension to MCM is straightforward from that result. Taking the logarithm of the evidence in Eq. ( A93 ) yields: \displaystyle\hskip-5.69054pt\log P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}_{icc})=\sum_{\boldsymbol{\alpha}\in(\mathbb{Z}/q\mathbb{Z})^{r}}\,\log\Gamma\left(k_{\boldsymbol{\alpha}}(\boldsymbol{\hat{\alpha}})\hskip-2.84526pt+\frac{1}{2}\right)-\log\Gamma\left(N+\frac{q^{r}}{2}\right)-\log\frac{\pi^{\frac{q^{r}}{2}}}{\Gamma\left(\frac{q^{r}}{2}\right)}\,, (A95) where the last term can be recognized as the geometrical complexity c_{icc}(r) of an ICC of rank r in Eq. ( A83 ). We assume that the dataset \boldsymbol{\hat{\alpha}} is sufficiently well-sampled, such that the empirical probability p_{\boldsymbol{\alpha}}=k_{\boldsymbol{\alpha}}(\boldsymbol{\hat{\alpha}})/N is non zero for all state (each state is observed at least a few times). We then take the expansion of the two log-gamma function for large N . This gives the following expansion of the log-evidence to the order of 1/N : \displaystyle\hskip-5.69054pt\log P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}_{icc})=N\,\sum_{\boldsymbol{\alpha}\in(\mathbb{Z}/q\mathbb{Z})^{r}}p_{\boldsymbol{\alpha}}\,\log p_{\boldsymbol{\alpha}}-\frac{K}{2}\log\left(\frac{N}{2\pi}\right)-c_{icc}(r)+O\left(\frac{1}{N}\right)\,, (A96) where K=q^{r}-1 is the number of parameters in the ICC. The first term in the expansion is the maximum log-likelihood of the ICC (see Property 42 ), in which p_{\boldsymbol{\alpha}}=k_{\boldsymbol{\alpha}}(\boldsymbol{\hat{\alpha}})/N is the empirical probability of state \boldsymbol{\alpha} in the dataset \boldsymbol{\hat{\alpha}} . The second term is the first complexity term in the MDL principle, penalizing models with a large number K of parameters. Comparing Eq. ( A96 ) with Eq. ( 8 ), one can see that selecting the MCM with the largest log-evidence, \log P(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}) , is equivalent at large N to selecting the MCM with the smallest description length, L(\boldsymbol{\hat{\alpha}}\,|\,\mathcal{M}) . Appendix E Additional Figures for data analysis examples E.1 Entropy of the variables in the data of the Big Five Personality Test. Figure A2: Entropy (in base q ) of the 50 variables in the Big Five Personality Test data for the two discretization schemes described in Sec. 6.4 with q=3 and q=5 . The two left panels give the value of the entropy in base q (or “qits”) for each variable for each discretization choice. The color indicates the magnitude of the entropy, which can vary between 0 and 1 qit. The variables are displayed in rows from left to right in the same order as in the original dataset 4 and each row corresponds to one trait (“Ex” for Extraversion, “ES” for Emotional stability, “A” for Agreeableness, “C” for Conscientiousness, and “OE” for Openness to experience). For example, in the raw data (i.e., scheme 1 with q=5 ), the previous to last variable is the least entropic and corresponds to the question “ I spend time reflecting on things ”. The right panel shows the average entropy (red curve) and minimal entropy (blue curve) obtained as one varies the value of \epsilon in Scheme 2. For the analysis in Sec. 6.4 , the value of epsilon was chosen to maximize the entropy of the least entropic variable (as indicated by the vertical dashed line). This is the same value of \epsilon that is used in the middle panel.