WorksMathematics
The maximum likelihood degree of no-three-way interaction models
Abstract
We prove that for all the maximum likelihood degree of the no-three-way interaction model of contingency tables is an integral with respect to the Euler characteristic over the matrices with nonzero entries modulo row and column scaling, where is the beta invariant of the matroid of the columns of [\Id_I\mid A]. By a theorem of Clarke, Hoşten, Kushnerchuk, and Oldekop, is the maximum likelihood degree of the independence model scaled by . Closed forms were previously known only when one variable is binary, and the formula recovers them. For fixed and the maximum likelihood degree is an exponential polynomial in ; the coefficient of its largest base is the maximum likelihood degree of the moduli space of points in linearly general position, which counts solutions to the generalized scattering equations of Cachazo, Early, Guevara, and Mizera. The same argument for a generically scaled model expresses the degree of as an Euler-characteristic integral of products of beta invariants. For matrices the integral reduces to counting strata of line arrangements, and the maximum likelihood degree of the model is ; in particular the model has maximum likelihood degree .
Introduction
The no-three-way interaction model for an contingency table consists of the distributions proportional to , and their limits: each pair of the three variables interacts, and there is no three-factor interaction [3, 4]. Its maximum likelihood estimate has no closed form and is computed iteratively, for instance by iterative proportional fitting [11, 10]. The algebraic complexity of the estimate is measured by the maximum likelihood degree: the number of complex critical points of the likelihood function on the model for generic data [13, 2]. Only when one variable is binary is it known in closed form. Améndola et al. conjectured that the maximum likelihood degree of the model is [2 Conj. 36], and Brysiewicz and Maraj proved this and gave a closed formula for every model by identifying it with a Lawrence lifting and expressing its maximum likelihood degree as an evaluation of a Tutte polynomial [5 Thm. 23, Cor. 32, Cor. 38]. They noted that the degree of the toric variety is 2457 and left the models with no binary variable to future work [5 Rem. 39]. In the binary case, the maximum likelihood estimate is also given by explicit determinants: for tables it is determined by a root of the determinant of a matrix, which gives an elementary proof that the maximum likelihood degree is , and for tables the likelihood equations form a multiparameter eigenvalue problem [14].
We give a formula for every model (Theorem 2.1):
where runs over the matrices with nonzero entries modulo row and column scaling, is the matroid of the columns of , is Crapo’s beta invariant [9], and the integral is with respect to the Euler characteristic [15]. By a theorem of Clarke, Hoşten, Kushnerchuk, and Oldekop [8], is the maximum likelihood degree of the independence model of an table scaled by , so the maximum likelihood degree of the three-way model is a signed Euler-characteristic sum of the -th powers of those of the scaled two-way models. For fixed and it is an exponential polynomial in , whose bases are the beta invariants that occur and whose coefficients are Euler characteristics of matroid strata.
The proof applies Huh’s theorem that the maximum likelihood degree of a smooth very affine variety is its signed Euler characteristic [13] to the model with its coordinate hyperplanes and the hyperplane removed, together with the observation that for a fixed interaction the model decomposes into independent slices whose contributions multiply. Theorem 2.1 is stated for the model scaled by any tensor , with replaced by ; for generic this gives the degree of the toric variety, and in particular an expression for the degree 2457 of (Corollary 4.1). The formula recovers the result of Brysiewicz and Maraj (Corollary 4.3): for the strata are indexed by set partitions of , and the integral becomes a Stirling-number sum equivalent to their Tutte-polynomial evaluation. Since the model is symmetric in its three variables, the formula also yields an identity between integrals over matrices of different shapes (Corollary 4.2).
Since depends only on the matroid, the integral is a finite sum of Euler characteristics of matroid strata. For matrices we compute them exactly, by fibering over the second column of : the fibers are strata of arrangements of lines through pairs of at most five points in the plane, whose combinatorics depends only on which three of these points are collinear. This gives the maximum likelihood degree of every model (Proposition 5.1); in particular the model has maximum likelihood degree 511. For matrices we evaluate the integral by counting points over finite fields; the counts are polynomial in for all primes tested, and their values at give a formula for the models (§ 5). Up to sign, the coefficient of the largest base is the Euler characteristic of the moduli space of points in linearly general position, whose likelihood equations are the scattering equations of Cachazo, Early, Guevara, and Mizera [6, 1]; hence the leading coefficient of the maximum likelihood degree in is the number of solutions of these equations (Proposition 6.1).
Statement
Fix integers . The no-three-way interaction model is the toric variety , the closure of the image of
More generally, for let be the closure of the image of , the model scaled by , so that , and write for its slices. Let be the union of the coordinate hyperplanes and the hyperplane . The maximum likelihood degree is the number of complex critical points of the log-likelihood function , where , on the smooth locus of .
For an matrix with nonzero entries, let be the matroid on elements represented by the columns of , and let be the beta invariant of Crapo [9],
The torus acts freely on by row and column scaling, and is constant on orbits; the quotient is identified with the torus of matrices with . The function is constructible, since the matroid strata are defined by the vanishing and nonvanishing of minors, and , since is connected on elements: each column of has full support, so and any column of form a circuit, and of a connected matroid on at least two elements is positive [9].
For a constructible function on a complex algebraic variety that takes finitely many values,
where is the topological Euler characteristic [15].
Theorem 2.1. For all and ,
where is the entrywise product. In particular,
When , is the maximum likelihood degree of the independence model of an table scaled by [8 Thm. 1.3] (this also follows from Lemma 3.5 below and Huh’s theorem), so the integrand is its -th power. Grouping matrices by the value of , Theorem 2.1 reads
an exponential polynomial in whose bases are the beta invariants that occur.
Proof of Theorem 2.1
We use two properties of the Euler characteristic of complex algebraic varieties: it is additive over finite partitions into locally closed subvarieties, and for a morphism ,
where is constructible [15]. Viro’s calculus uses the Euler characteristic with compact supports, which for complex algebraic varieties coincides with (see [7] and the references there). In particular is multiplicative on products, and .
The proof proceeds in four steps. We first identify with a smooth hypersurface in a torus (Lemma 3.1) and apply Huh’s theorem. Projecting onto reduces to the Euler characteristic of a level set of a sum of homogeneous functions, which factors into single-slice contributions (Lemmas 3.2 and 3.3); each slice then evaluates to a signed beta invariant via hyperplane arrangement complements (Lemmas 3.4 and 3.5).
Lemma 3.1. Let and let have coordinates (), (), and , and put . Then is isomorphic to the hypersurface
which is smooth, of dimension .
Proof. The map , , is injective with an inverse given by monomials on its image: with , , , and . Every in the full torus can be rescaled by , , , which preserves every product , so as to satisfy . Hence is the image of the full torus, a translate of a closed subtorus of that is stable under scaling (by scaling ); it is therefore , where is the affine cone over , and is an isomorphism onto it. A point of has a unique representative in this cone with , and . The function is homogeneous of degree one under , so on , and there. □
By Lemma 3.1, is smooth, so it coincides with the set on which critical points are counted, and through the coordinates it is a closed subvariety of , namely the torus coset intersected with . On the term vanishes, and since the log-likelihood is invariant under scaling , its critical points on correspond to the critical points on of the master function . By Huh’s theorem [13 Thm. 1] (see also [8 Thm. 2.3] for this form), for generic
Lemma 3.2. For let . Then .
Proof. For , is a point. For project to . Over the fiber is , and trivializes this family over . Over the fiber is empty for and isomorphic to for , by , so its Euler characteristic is 0. Hence . □
Lemma 3.3. For let be a variety with an algebraic -action and a regular function with . Put and . Then and
Proof. The map is an isomorphism , so . Partition the set on the left by , which is nonempty. The part with a given is isomorphic to , by , with inverse , where for y_k=v_k\cdot e_k$ for . By Lemma 3.2 the left side is
:::
Lemma 3.4. Let span , let be their matroid, and let be the complement of the hyperplanes . Then .
Proof. We use the following properties of [9]: if is neither a loop nor a coloop; if has a loop, or a coloop and at least two elements; and if is loopless of rank one. If has a loop, is empty. If and is loopless, is a point. For induct on , for all ranks simultaneously. If every element is a coloop, and . Otherwise choose neither a loop nor a coloop; then has rank and has rank . Then is the disjoint union of and the complement in the hyperplane of the traces of the remaining hyperplanes, which is , since the trace of on is defined by the image of in . Hence .
Lemma 3.5. For an matrix with nonzero entries let and . Then .
Proof. Project to and put . If , the fiber is , which is isomorphic to by for and the identity on for when , and is empty when . Its Euler characteristic is if and otherwise, and it is constant on the locally closed sets of with a given . By (1), , where
is the complement in of the hyperplanes whose normal vectors are the columns of . By Lemma 3.4, .
Proof of Theorem 2.1. Project to . The fiber over is , where is the function of Lemma 3.5 for the matrix on , with acting on the factor. Since is a torus of positive dimension, , and Lemmas 3.3 and 3.5 give the fiber Euler characteristic
By (1) and (2),
and .
Consequences
Corollary 4.1 (Degree). For generic ,
Proof. For a generic scaling the maximum likelihood degree of a toric variety equals its degree [2 Cor. 8]; apply Theorem 2.1.
Brysiewicz and Maraj noted that they have no combinatorial interpretation of the degree 2457 of [5, Rem. 39; Corollary 4.1 expresses it as an Euler-characteristic integral of products of beta invariants over the common refinement of the matroid stratifications of the matrices . For example, for write in terms of and let be the odds ratio of . Then unless , where it is 1. For generic the are distinct, the stratum has Euler characteristic , and the integral is , so [2 Prop. 34].
Corollary 4.2 (Symmetry). For all ,
where ranges over and over matrices with first row and column equal to 1.
Proof. Both sides equal , by Theorem 2.1 applied to and to the isomorphic model . □
The symmetry in and is visible directly: the matrix represents the dual of with the same labels, and after scaling the first block by and exchanging the two blocks it becomes , which represents ; transposition maps the chart onto the chart, and for matroids on at least two elements [9]. The symmetry between and is not apparent from the integral.
Corollary 4.3 (Brysiewicz and Maraj [5 Cor. 32 and Cor. 38], in an equivalent form).
where is a Stirling number of the second kind.
Proof. For , is determined by with , and consists of the points , , and of . If the take distinct values, is a rank-2 matroid whose simplification is the uniform matroid on elements, so (deleting a parallel element in a loopless matroid leaves unchanged, since contraction produces a loop). The matrices inducing a given partition of into blocks are parametrized by the values of the blocks not containing 1: distinct points of , whose configuration space has Euler characteristic . There are partitions, and the sign is . □
Three-level variables
For , the matroid is that of points in : the coordinate points and the columns of . When the columns are distinct and no three of the points are collinear, is uniform of rank three and ; this is the largest value that occurs, since is the maximum likelihood degree of the scaled independence model [8 Thm. 1.3], which is at most the degree of [2 Cor. 8].
We use two facts about . If is a simple matroid of rank three on elements represented over , then
the sum over the lines of with at least three elements. By Lemma 3.4, is the Euler characteristic of the complement in of the lines dual to the elements, which is , the sum now over all rank-two flats, the points where of the lines meet; and . Second, if and are parallel elements of a matroid without loops, then , since is not a loop, is not a coloop because spans it, and has the loop .
Proposition 5.1. The weights are , and for . Consequently, for all ,
in particular .
Proof. Write with and , and regard as points of ; is their matroid. We apply (1) to each set and the projection ; the fibers of the projection are copies of the torus of points . For each let be the Euler characteristic of the set of in the torus with . We show below that depends only on which of three types belongs to; then is the sum over the types of the Euler characteristic of the set of such times . We record via the exponential polynomial .
Let . Since and have no zero coordinate, three points of are collinear only if they are for some , that is, if lies on one of the lines , , through and , respectively, which meet only at . This gives three types of : the three sets of on the line through and , each isomorphic to , with ; the point ; and the complement of the three lines, with .
For fixed , let be the arrangement of lines spanned by pairs of points of . The matroid is determined by the set of lines of that contain , since equals a point of exactly when it lies on two lines through . Two lines of share at most one point of ; if three lines passed through a point outside , the sets of points of on them would be pairwise disjoint, which needs six points. Hence the points lying on at least two lines of , which we call intersection points, are the points of and, outside , the points where two lines containing disjoint sets of points of meet, each of which lies on exactly two lines. By additivity, the open part of a line , the set of points on and on no other line, has Euler characteristic minus the number of intersection points on , and the complement of has Euler characteristic minus the sum of the Euler characteristics of the open parts minus the total number of intersection points. The point lies in the torus exactly when it avoids the three coordinate lines ; in particular, since each intersection point outside lies on exactly two lines, it lies in the torus unless one of its two lines is a coordinate line. All the counts below are combinatorial, so is constant on each type of .
If , no three points of are collinear, has 10 lines, and there are 15 intersection points outside , so that each line contains five intersection points, two of them in ; nine of them lie on the coordinate lines, each of which meets the three lines spanned by the other three points. By (3) with the parallel-element rule, the strata of are:
the complement of (, );
the open parts of the seven noncoordinate lines ( each, );
the six intersection points in the torus (, );
the two points (, , for five points with no three collinear).
Thus .
If , permuting the coordinates of we may take . Then consists of the line through , the three coordinate lines, and the four lines . The pairs of lines with disjoint sets of points of give seven intersection points outside : , the four points where meets and meets , and the two points and , which lie in the torus. The line contains three intersection points and every other line four. By (3) with the parallel-element rule, the strata of are:
the complement of (, );
the open parts of ( each, );
the open part of (, ) and the two intersection points in the torus (, );
the two points (, ).
Thus , the terms in canceling.
If , then by the parallel-element rule, so is , by Corollary 4.3 and the symmetry noted after Corollary 4.2.
Adding 2 times the first of these, times the second, and the third gives the stated weights, and Theorem 2.1 with gives the formula. □
For we evaluate the weights by counting points over finite fields. The numbers of points over of the strata , with computed from the ranks of submatrices over , agree for each with a polynomial in of degree at most 6 for all primes , including at least two primes beyond those needed to determine it. If the numbers of points are given by these polynomials for all sufficiently large finite fields, the value of the polynomial at 1 is the Euler characteristic of the stratum, by a theorem of Katz [12, Thm. 6.1.2.3; see Thm. 2.1.8]. The entries for in Table 1, and the formula and values derived from them below, rest on this polynomiality, which we have verified for the primes listed.
Table 1. The weights , the Euler characteristics of the sets of with . For they are those of Corollary 4.3, using ; for they are given by Proposition 5.1; for they are the values at of the point counts.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 | 2 | |||||||||
| 1 | 6 | 36 | 26 | |||||||
| 1 | 14 | 204 | 252 | 4878 | 1272 |
Table 1.
With these weights, Theorem 2.1 gives
Table 2 lists the first values of this formula and of Proposition 5.1.
Table 2. Maximum likelihood degrees of the and models.
| 2 | 3 | 4 | 5 | 6 | ||
| 31 | 511 | 5755 | 52711 | 426811 | ||
| 115 | 5755 | 172951 | 3797491 | 68382295 |
Table 2.
These values are consistent with the symmetry of the model. For they agree with the and values of Corollary 4.3, and the and models, computed from different weights, both give 5755. The weights , computed in the same way, coincide with , as the remark following Corollary 4.2 requires. For every formula gives 1, the maximum likelihood degree of the saturated model.
The leading term
The leading coefficient is an Euler characteristic that appears in the theory of generalized scattering amplitudes. Let be the moduli space of points in linearly general position in , the quotient by of the open subset of the Grassmannian where all Plücker coordinates are nonzero [6]. It is a smooth very affine variety of dimension .
Proposition 6.1. For every , , with equality if and only if every minor of is nonzero, and the set of such is isomorphic to . Consequently, as ,
Proof. By [8 Thm. 1.3], is the maximum likelihood degree of the independence model of an table scaled by , whose degree is . By [2 Thm. 2] the maximum likelihood degree is smaller than the degree exactly when the scaling is a zero of the principal -determinant, which for is the product of all minors of the scaling matrix [8 Prop. 2.1]. A point of with all Plücker coordinates nonzero is the row space of a unique matrix , whose maximal minors are, up to sign, the minors of ; scaling the columns of and then restoring the identity block by scaling rows acts on by row and column scaling. Hence the set of with all minors nonzero is , and its Euler characteristic is the coefficient of the largest base in Theorem 2.1. Since , Huh’s theorem gives . The other bases in Theorem 2.1 are integers smaller than , which gives the error term. □
The leading coefficient is positive in every case in which it is known. For , is the moduli space of points on the line, whose maximum likelihood degree is , the top term of Corollary 4.3. For , the maximum likelihood degrees of for are 2, 26, 1272, 188112, and 74570400 [6, 1]; they are the numbers of solutions of the scattering equations on . The first three are the last entries of the rows of Table 1, and the next two are the leading coefficients of and . In particular, a closed formula for the maximum likelihood degree of the model would give one for the Euler characteristic of . The duality [6] identifies with , in accordance with the symmetry of the model in and ; the first case not covered by is the self-dual , which governs the models, and whose maximum likelihood degree was computed numerically to be 5211816, with a certified lower bound of 5211598 [1 Thm. 6.1].
References
References
- [1]D. Agostini, T. Brysiewicz, C. Fevola, L. Kühne, B. Sturmfels, and S. Telen, Likelihood degenerations, with an appendix by T. Lam, Adv. Math. 414 (2023), Paper No. 108863, doi:10.1016/j.aim.2023.108863.DOI
- [2]C. Améndola, N. Bliss, I. Burke, C. R. Gibbons, M. Helmer, S. Hoşten, E. D. Nash, J. I. Rodriguez, and D. Smolkin, The maximum likelihood degree of toric varieties, J. Symbolic Comput. 92 (2019), 222–242, doi:10.1016/j.jsc.2018.04.016; numbering as in arXiv:1703.02251.DOI
- [3]M. W. Birch, Maximum likelihood in three-way contingency tables, J. Roy. Statist. Soc. Ser. B 25 (1963), no. 1, 220–233, doi:10.1111/j.2517-6161.1963.tb00504.x.DOI
- [4]Y. M. M. Bishop, S. E. Fienberg, and P. W. Holland, Discrete Multivariate Analysis: Theory and Practice, MIT Press, Cambridge, MA, 1975; reprinted by Springer, New York, 2007, doi:10.1007/978-0-387-72806-3.
- [5]T. Briesewicz and A. Maraj, Lawrence lifts, matroids, and maximum likelihood degrees, Algebr. Stat. 16 (2025), no. 2, 217–242, doi:10.2140/astat.2025.16.217; numbering as in arXiv:2310.13064.
- [6]F. Cachazo, N. Early, A. Guevara, and S. Mizera, Scattering equations: from tropical Grassmannians to tropical Grassmannians, J. High Energy Phys. (2019), no. 6, 039, doi:10.1007/JHEP06(2019)039.DOI
- [7]S. E. Cappell, L. Maxim, and J. L. Shaneson, Euler characteristics of algebraic varieties, Comm. Pure Appl. Math. 61 (2008), no. 3, 409–421, doi:10.1002/cpa.20201; arXiv:math/0606654.DOI
- [8]O. Clarke, S. Hoşten, N. Khusrenchuk, and J. Oldekop, Matroid stratification of ML degrees of independence models, Algebr. Stat. 15 (2024), no. 2, 199–223, doi:10.2140/astat.2024.15.199; numbering as in arXiv:2312.10010.DOI
- [9]H. H. Crapo, A higher invariant for matroids, J. Combinatorial Theory 2 (1967), 406–417, doi:10.1016/S0021-9800(67)80051-6.DOI
- [10]I. Csiszár, I-divergence geometry of probability distributions and minimization problems, Ann. Probab. 3 (1975), no. 1, 146–158, doi:10.1214/aop/1176996454.DOI
- [11]W. E. Deming and F. Stephan, On a least squares adjustment of a sampled frequency table when the expected marginal totals are known, Ann. Math. Statist. 11 (1940), no. 4, 427–444, doi:10.1214/aoms/1177731829.DOI
- [13]J. Huh, The maximum likelihood degree of a very affine variety, Compos. Math. 149 (2013), no. 8, 1245–1266, doi:10.1112/S0010437X13007057.DOI
- [14]S. Sivarajan, An explicit determinantal formula for limits of iterative proportional fitting with a binary variable, hexagon:2611.00705 (2026).
- [15]O. Ya. Viro, Some integral calculus based on Euler characteristic, in: Topology and Geometry, Rohlin Seminar, Lecture Notes in Math. 1346, Springer, Berlin, 1988, 127–138, doi:10.1007/BFb0082775.