Counting the Fixed Points of Binary Belief Propagation: Generic Degree, Syzygies, and Real Solutions

1 Introduction

• For generic parameters, the admissible complex BP degree equals a graph state sum over edge sets without degree-one vertices.The paper motivates the count by noting that positive fixed points can depend on initialization and that the generic degree bounds real and positive fixed-point counts.Source: §1 · pp. 1–2

1.1 Two main results

• The universal edge-incidence ring realizes the state sum in its graded Betti table, while strong-field boundary charts realize state weights as ramification indices and exhaust the complex fiber.At sufficiently strong field, the charts give exactly Q(G) simple roots; for maximum degree at most three, the minimum real count equals the number of minimal module generators.Source: §1.1 · pp. 2–4, §1 · p. 2
• The ring’s alternating numerator recovers a graph polynomial, and a regular-sequence Artin reduction yields the one-variable specialization with a correction for tree components.Without tree components, the Artin Hilbert series is ω_G; for trees, N(G) = 1 and the ring is isomorphic to S_G.Source: §1.1 · p. 3
• At every external field, each Eulerian edge subset supports at least one admissible real root, and sufficiently strong fields attain the resulting lower bound.The strong-field charts also give the complex, real, and positive root counts, and all complex roots are simple.Source: §1.1 · p. 3

1.2 A running example

• For K4, the generic complex degree is 48, the minimum real count is 8, and the ring has 8 minimal generators indexed by the empty state and cycles.The Artin reduction has Hilbert series 1 + 2t + 3t^2 + 8t^3 + 16t^4 and length 30.Source: §1.2 · p. 4

1.3 Related work

• The paper situates its results alongside work on positive BP fixed points, homotopy-continuation enumeration, generalized loops, graph polynomials, and homological message passing.It identifies the graph polynomials as those of Watanabe and Fukumizu and the geometric method for syzygies as following.Source: §1.3 · p. 4

1.4 Organization

• The paper’s roadmap assigns the generic degree, ring resolution, strong-field complex count, and real-sector analysis to sections 2 through 5, respectively.Supplementary material collects notation, omitted elementary proofs, and a longer related-work comparison.Source: §1.4 · p. 4

1.5 Formalization

• The degree, selected ring and resolution statements, and real counts are formalized in Lean 4 with mathlib.Some proofs differ from the paper’s arguments, and the K4 Gröbner-basis computation is external; the repository records formal hypotheses and declarations.Source: §1.5 · p. 4

2.1 Coordinates and the open set being counted

• The admissible equations define a smooth, irreducible family that is finite étale of positive degree over a nonempty Zariski-open parameter set.The count excludes roots that cannot be normalized to beliefs, including those with a vertex ratio equal to −1.Source: §2.1 · p. 5

2.2 Auxiliary edge coordinates

• Auxiliary edge coordinates recover the original BP scheme on its admissible open set and preserve root multiplicities.Choosing square roots of fixed edge parameters does not multiply a fiber’s root count.Source: §2.2 · p. 6

2.3 Excluding all weak-coupling boundary limits

• Under the stated boundary assumptions, every admissible solution avoids weak-coupling limits in which a transformed vertex ratio reduces to −1.The boundary exclusion applies even when the vertex parameters depend on t.Source: §2.3 · pp. 7–8

2.4 The limit states and their unique lifts

• Each limit state has exactly one simple admissible lift, so the generic degree equals the number of limit states, with each contributing vertex factor determined by its active-edge degree.The degree is multiplicative under disjoint union, unchanged by attaching a leaf or subdividing an edge, one on forests, and two on connected single-cycle graphs.Source: §2.4 · pp. 8–9
• The generic-degree theorem applies on a nonempty Zariski-open parameter set and does not determine special fibers.Section 4 gives a separate complete count for each fixed coupling vector with a_e^2 ≠ 1.Source: §2.4 · p. 9

3.1 Edge bundles and the state cohomology

• Contributing edge states have cohomology concentrated in one degree, with dimension equal to their state weight; their state-indexed terms construct the graph’s resolution.States containing a vertex of degree one have zero cohomology, and a contributing state attains the upper bound q − j = ρ.Source: §3 · p. 10, §3.1 · p. 11

3.2 The universal incidence scheme

• The universal incidence scheme is a rank-3m vector bundle over XG, and its global-function ring UG is finite over SG with degree-zero part C.The projection to the coefficient space is proper.Source: §3.2 · p. 11

3.3 The complete minimal resolution

• UG has a minimal graded SG-resolution of length ρ indexed by edge states, and its total Betti number equals the generic admissible BP degree.Its Tor algebra is canonically identified with the state cohomology algebra, whose product combines cup product and exterior multiplication.Source: §3.1 · p. 11, §3.3 · pp. 12–13

3.4 Normality and Cohen–Macaulayness

• UG is a normal Cohen–Macaulay domain of dimension dG = 3m + n − τ.Here τ counts tree components, including isolated vertices.Source: §3.4 · p. 13

3.5 Graph maps and the Tor product

• The Tor algebra is functorial for noncontracting graph maps, and when no two edge-disjoint simple cycles meet at a vertex, its minimal generator count equals the minimum real admissible BP fixed-point count.The equality holds in particular for graphs of maximum degree at most three; the minimum is over external fields for fixed finite nonzero real couplings.Source: §3.5 · pp. 14–15

3.6 The graph polynomials and Artin reductions

• For the graph polynomials of Watanabe and Fukumizu [11], a regular-sequence Artin reduction has Hilbert series eωG(t) = ωG(t)(1 − t)^τ, and dimension eωG(1).When there are no tree components, ωG itself is the Artin Hilbert series.Source: §3.6 · pp. 15–16

3.7 The complete graph on four vertices

• For K4, the ring has eight minimal module generators, total Betti number 48, and an Artin reduction of length 30 with Hilbert series 1+2t+3t^2+8t^3+16t^4.The eight generators are the unit, four triangle classes, and three four-cycle classes; products of nonunit classes vanish in the quotient by S+UK4.Source: §3.7 · p. 16
• Theorems 3.4, 3.6, 3.7, and 3.10, together with Theorem 2.5, establish the algebraic assertions of Theorem 1.1.Source: §3.7 · p. 17

4 The strong-field boundary of the BP family

• The statewise power-map model extends the fixed-a admissible BP family smoothly and analytically across p = 0.Its charts produce wt(S) distinct simple solutions for each state, with solutions from different states distinct.Source: §4 · p. 17

4.1 Two edge branches near the boundary

• Near the boundary, each edge has analytic message branches; at the selected branch the residual-message Jacobian is the identity, enabling the implicit function theorem.The branch construction’s Singular check is a finite-characteristic specialization with multiplicity, not a certification of 48 rational points or simplicity.Source: §4.1 · p. 17

4.2 Absorbing the analytic units

• Absorbing analytic units gives an exact power-equation model, and its reconstructed solutions remain admissible with invertible BP Jacobian.Different states are distinguished by which messages tend to zero.Source: §4.2 · pp. 18–19

4.3 Exhaustion of the complex fiber

• For each state S, the strong-field chart supplies wt(S) distinct simple admissible solutions, and all states’ charts together exhaust the complex fiber for sufficiently small nonzero fields.The fiber then has exactly Q(G) points, all simple, with no additional isolated or positive-dimensional components.Source: §4 · p. 17, §4.3 · p. 19

4.4 Boundary algebras and state factors

• At the boundary p = 0, each state chart has a complete-intersection local algebra of length wt(S), with ramification index r_i in its ith boundary direction.Statewise, these lengths and indices match the factors in the cohomology table; the comparison does not identify the algebras’ multiplications or a deformation between states.Source: §4.4 · pp. 19–20

5.1 A maximum principle for the vertex ratios

• At any admissible real solution with positive physical parameters, all vertex ratios are positive and negative messages occur in matching pairs on an Eulerian edge set.These sign conclusions do not require a finite fiber or nondegeneracy; the Eulerian sets are the elements of H1(G; F2).Source: §5.1 · p. 20

5.2 Two branches on an edge

• For prescribed positive vertex ratios and each edge with a_e > 0 and a_e ≠ 1, the edge equations have exactly two real admissible solutions: one positive-message and one negative-message branch.Both branches depend real analytically on the ratios and have invertible edge Jacobians.Source: §5.2 · p. 21

5.3 The global vertex map

• For fixed finite nonzero J, every Eulerian sector contains an admissible real BP solution for every h ∈ RV.If every admissible real root with negative-edge support S is nondegenerate, the roots are finite in number and their number is odd.Source: §5.3 · pp. 21–22

5.4 Attainment at strong fields

• At sufficiently strong fields, the admissible complex fiber has Q(G) simple points, exactly 2ν(G) real points—one per Eulerian sector—and exactly one positive point.For every external field, each sector contains at least one real solution, so strong fields attain the minimum real count.Source: §5.3 · p. 21, §5.4 · pp. 22–23
• The nonzero-coupling assumption matters: a zero-coupling edge carries messages 1 and can be deleted, so the lower bound then uses the support graph’s cycle rank.At generic finite étale physical parameter points, the real count lies between 2ν(G) and Q(G), while the positive count lies between 1 and Q(G) − 2ν(G) + 1.Source: §5.4 · p. 23

Discussion

• The edge-incidence ring retains degrees, products, and graph maps, while strong-field charts realize state weights as BP boundary-algebra lengths and distinguish states with real branches.The discrepancy between module generators and real branches comes from Eulerian states with a vertex of degree at least four; open questions include higher Tor products, resolution differentials, and naturality under edge contractions.Source: Discussion · p. 23

• Language-model tools assisted with drafting, reorganizing, and checking proofs and text, and with preparing computational checks; the author assumes responsibility for all content.Source: Declarations · p. 24

• The table groups notation for graph state weights and polynomials, BP parameters and rescalings, the edge-incidence ring and Artin section, boundary local data, and root counts.Source: Notation · p. 25

Elementary properties of the degree

• A selected leaf edge contributes zero, while subdividing an edge preserves the nonzero state weights; consequently a unicyclic component reduces to a cycle with only empty and full states contributing.Source: Elementary properties of the degree · p. 25

The non-normalizable locus

• On a connected graph, solutions without normalization either have all 1 + F_i nonzero or have F_i = −1 at every vertex.The all-minus-one locus is generically empty for trees and, when cycle rank is positive, is smooth of pure dimension ν(G) − 1.Source: The non-normalizable locus · p. 25
• The all-minus-one solutions are parametrized by an open subset of a torus with 2m dimensions, and their parameter map is dominant when ν(G) ≥ 1.Source: The non-normalizable locus · pp. 25–26
• Generic smoothness gives the all-minus-one locus dimension ν(G) − 1 when cycle rank is positive, whereas its generic fiber is empty for a tree.Source: The non-normalizable locus · p. 26

The incidence scheme as a vector bundle

• The universal incidence scheme is the total space of a rank-3m vector bundle, with the edge equations forming a regular sequence; projectivity then gives finiteness over coefficient space.Source: The incidence scheme as a vector bundle · p. 26

Cohen–Macaulayness at every prime

• Localization of the resolution shows that the edge-incidence ring is Cohen–Macaulay at every prime, not only at the homogeneous maximal ideal.Source: Cohen–Macaulayness at every prime · p. 26

Functoriality

• Pullback along noncontracting graph maps induces natural maps of Tor algebras that preserve products, without requiring flatness of the coefficient-ring map.Source: Functoriality · p. 27

The cycle-compatibility algebra

• Degree-zero Tor classes correspond to collections of vertex-disjoint cycles: their products vanish when cycles intersect and remain nonzero when cycles are disjoint.Source: The cycle-compatibility algebra · p. 27

Module generators and real sectors

• For graphs of maximum degree at most three, every even edge support has degrees zero or two, so the cycle-indexed generators account for the binary cycle space.Source: Module generators and real sectors · p. 27

One-dimensional sections

• Regular coefficient cuts preserve the Betti table, and the resulting Artin section has total Betti number N(G); its isomorphism class may depend on the cuts.Source: Three invariants of one resolution · p. 27, One-dimensional sections · p. 28

Sharp bounds at fixed cycle rank

• The sharp bounds at fixed cycle rank are attained by simple graphs: the lower bound by ν triangles sharing one vertex and the upper bound by a ladder of ν squares.The upper bound is attained exactly when the 2-core has maximum degree at most three; trees attain both bounds when ν = 0.Source: Sharp bounds at fixed cycle rank · p. 28

The objects being compared; The Gröbner-basis check for K4

• The Artin length and total Betti number are distinct invariants, and the equality of Q(G) with the BP degree does not identify an Artin section with a BP root algebra.A K4 finite-characteristic specialization has saturated ideal length 48, but the proof of N = Q does not depend on that check; naturality also excludes general edge contractions.Source: The objects being compared · pp. 28–29, The Gröbner-basis check for K4 · p. 30

The algebra at a state

• Each state algebra has a free basis over the convergent parameter ring, and its length after setting p = 0 equals the ramification index from the ith power equation.The basis uses exponents 0 ≤ a_i < r_i.Source: The algebra at a state · p. 30

Duality and coordinate choices

• The duality pairing identifies B with its vector-space dual, but its coordinate dependence prevents a canonical algebra identification with the Tor summand.Here B = C[w]/(w^r), with r = k − 1.Source: Duality and coordinate choices · p. 30

The eight real states of K4

• For K4, the state types yield 48 complex branches and eight real states, with one positive state; the eight real states are the empty set, four triangles, and three four-cycles.In the stated chamber, the six K4 − e states and the full state have no real branches.Source: The eight real states of K4 · pp. 30–31

The two real edge branches

• The edge quadratic has one positive and one negative root, and both reconstruct admissible message pairs without hitting the excluded denominators.The negative root lies strictly between −1 and −1/s.Source: The two real edge branches · p. 31
• The two edge branches are real analytic, and the edge Jacobian is invertible under the stated nonvanishing conditions.Solving the second equation for the opposite message and then the first by a simple quadratic yields the branches.Source: The two real edge branches · p. 31

Vertex coordinates on a sector

• Prescribing positive vertex coordinates and selecting negative branches on an Eulerian support produces admissible BP roots satisfying the sector equations.Conversely, every admissible real root recovers those coordinates and its Eulerian support; local solution spaces and Jacobian nondegeneracy are preserved.Source: Vertex coordinates on a sector · p. 31

A degree budget for positive solutions

• The total of Q(G) complex roots bounds positive roots after at least one nonpositive real root is counted in each nonempty Eulerian sector.There are 2^ν(G) Eulerian subsets, and the empty sector supplies at least one positive root.Source: A degree budget for positive solutions · p. 32

Zero couplings

• The cycle-rank lower bound requires nonzero couplings; when some coupling vanishes, the real solution count instead uses the cycle rank of the support graph after deleting zero-coupling edges.Deleting those edges gives a bijection of admissible real solution sets with the resulting support graph.Source: Zero couplings · p. 32

Further comparison with related work

• Unlike positive-message variational classifications, the sign-sector count includes admissible negative messages, indexed by Eulerian edge sets.The cited variational and signed-graph results concern positive messages.Source: Further comparison with related work · p. 32
• The paper’s generic degree is for its admissible Ising-parameter family, not a numerical comparison with a generic-support BKK bound; its Betti total and Artin-reduction length are also distinct invariants.The universal edge-incidence ring and BP fiber algebra serve different roles.Source: Further comparison with related work · pp. 32–33
• The sheaf-theoretic Koszul complex controls a resolution, while the strong-field BP connection uses shared state weights and local power maps; no identification with other message-passing complexes or graph-homotopy invariance is asserted.Source: Further comparison with related work · p. 33