Introduction
A graphon is determined by the homomorphism densities of all finite graphs [33 , 11 , 12 , 16 ] . This is the warrant behind every method that summarizes a network by motif counts. In practice such methods count finitely many patterns, usually on a handful of vertices, and the theory that licenses the truncation says little about what a particular truncation costs. We compute the cost exactly in one natural family, and then follow it through three ways of reading the same graph: a bounded-order motif census, the full law of the graph, and the spectral pipelines used in practice.
The family is the latent structure block model (LSBM), a random dot product graph (RDPG) whose latent positions lie on K K K rays through the origin [56 , 5 , 6 , 44 ] . A node’s community fixes the slope of its ray and a random radius fixes its position along it. Equivalently, it is a degree-corrected stochastic blockmodel (DCSBM) [26 ] whose degree parameters are the radii and whose connectivity matrix B k l = 1 + s k s l B_{kl} = 1 + s_k s_l B k l = 1 + s k s l has rank two; under the DCSBM, communities appear in the spectral embedding as rays (Sanna Passino et al., 2022). We work in the symmetric random-slope family: slopes come in reflection pairs with equal weights, and all communities share one radial law. The symmetry is deliberate. It is the least favorable setting for exhibiting a fiber, since it leaves the fewest free directions; relaxing it does not remove the fiber, only its closed form (Section 9). It also makes every homomorphism density, for a fixed radial law, a polynomial in the moments m j m_j m j of the squared slope. Identifiability under motif counting becomes a question about a polynomial map, and the set of configurations the census of order m m m conflates with a given one is the fiber of the census map through it.
Our theorem (§ 3 ) answers the question for every K ≥ 3 K \ge3 K ≥ 3 . The census of order 2 K − 2 2K - 2 2 K − 2 determines m 1 , … , m K − 2 m_1,\ldots,m_{K-2} m 1 , … , m K − 2 and nothing more, so the fiber through an admissible configuration is a curve; we give it in closed form as an arc whose endpoints are classical quadrature rules, show that nothing else in the family matches, and identify the friendship graph F K − 1 F_{K-1} F K − 1 on 2 K − 1 2K - 1 2 K − 1 vertices as the unique edge-minimal separator. What is blind is governed by degree rather than size: every graph of maximum degree at most 2 K − 3 2K - 3 2 K − 3 has constant density along the fiber, however many vertices it has. Because the threshold grows with K K K , no fixed motif order serves the whole family. The moment-problem machinery is classical; what is new is the reduction of motif matching to it, and the exhaustive, closed-form description that results.
At the threshold the separation is present but minute, for a structural reason. Any motif reads m j m_j m j through terms at most m 1 2 j m_1^{2j} m 1 2 j , and F K − 1 F_{K-1} F K − 1 attains the bound; at K = 4 K = 4 K = 4 that is about 10 − 4 10^{-4} 1 0 − 4 , and two configurations differing by 45.1% in m 3 m_3 m 3 differ by 7.6 × 10 − 7 7.6 \times10^{-7} 7.6 × 1 0 − 7 in t ( F 3 ) t(F_3) t ( F 3 ) . Detection from motif counts would take about 2 × 10 15 2 \times10^{15} 2 × 1 0 15 nodes in a single graph (10 12 10^{12} 1 0 12 –10 13 10^{13} 1 0 13 even pooling 200 graphs), and the obstruction is invariant to edge density (§ 5 ). Lower-order statistics are blinder still: trees, and hence message-passing graph neural networks, which distinguish graphons exactly as tree densities do ([10 ] ), see nothing of the slopes at all (Theorem 3.3). Yet the information is in the graph: its law identifies the configuration, and model-based fits recover the position along the fiber (§ 6 ). The fiber belongs to the pair (model, statistic), not to the model.
The fiber resurfaces where nothing counts motifs. Spectral pipelines for the DCSBM embed the adjacency matrix, reduce each node to a direction (a ratio of eigenvector entries, an angle, or a unit vector), cluster, and read the parameters off the clusters ([25 , 40 , 29 ] (Sanna Passino et al. 2022)). Adjacency spectral embedding is consistent; the loss is in the summary taken afterward. On graphs simulated from the family, in an intermediate regime the error of such pipelines collapses onto the fiber and slides along it by more than a third of its length, with replicate spread 5–14 times smaller than the displacement, and nominal 95% regions contain the truth in no cell of 17 of 18 groups (§ 7 ). Concretely, a community holding 3.75% of the nodes is reported at about 17%, every replicate lies within 2% of the arc of the truth’s census fiber, and no nominal 95% region contains the truth. Two of three published pipelines slide this way, by up to 58% of the arc; the third avoids the slide in that regime but fails bimodally near the fiber’s endpoint, and a standard preprocessing filter restores the slide. Model-based fits, given the ray family and the embedding’s noise model—a ray mixture under the ASE covariance, and the LSBM authors’ Bayesian sampler—are accurate at every cell tested.
We present this as a caution with a remedy: the algorithms are correct, the interpretation of their output is at risk, and the risk can be checked and avoided. Section 8 gives four checks—whether a fit sits in the displacement regime, what to run instead, why a confidence interval will not raise the alarm, and how wide the remaining ambiguity is.
Contributions. (i) A non-identifiability theorem for every K ≥ 3 K \ge3 K ≥ 3 with the fiber in closed form: existence, shape, size, and cost. (ii) A hierarchy of what bounded-order statistics see: message passing nothing, graphs of maximum degree at most 2 K − 3 2K - 3 2 K − 3 nothing along the fiber, F K − 1 F_{K-1} F K − 1 the fiber at a 10 − 4 10^{-4} 1 0 − 4 suppression. (iii) Evidence that no information barrier is responsible. (iv) An account of spectral pipelines on the fiber: published methods are displaced along it with silent confidence regions; a regime map; and practitioner checks.
Related Work
RDPGs and spectral estimation. Adjacency spectral embedding (ASE) is consistent for RDPG latent positions up to orthogonal transformation [48 ] , clusters perfectly for large n n n [34 ] , and obeys row-wise central limit theorems [4 , 50 ] and two-to-infinity bounds [13 ] ; see also [42 ] . For latent structure, one embeds and then estimates the support of the embedded cloud [6 , 51 , 41 , 44 ] . For the DCSBM, spectral clustering reduces each node to a direction: SCORE takes entrywise ratios of eigenvectors [25 ] , others normalize rows [40 , 29 ] or pass to spherical coordinates [44 ] . Their guarantees concern community labels; we study the parameters read off the clusters. These are consistency and first-order statements. Plug-in summaries of noisy embeddings carry second-order bias: noise inflates second moments, the attenuation effect of errors-in-variables models [19 , 14 ] , and higher-order spectral theory with explicit bias terms is emerging [54 , 57 , 30 ] . What is new here is the amplifier: a flat direction of the population objective turns a second-order bias into an O ( 1 ) O(1) O ( 1 ) displacement along the fiber.
Graphons, densities, identifiability. Densities of all finite graphs determine a graphon up to weak isomorphism [33 , 12 ] , but the inverse counting lemma controls cut distance from densities up to order k k k only at rate O ( 1 / log k ) O(1/\sqrt{\log k}) O ( 1/ log k ) [11 , 32 ] . Densities are a determinate but badly conditioned chart. For the K K K -block SBM, Bickel et al. [9 ] show that wheel densities identify the parameters when π , F π , … , F K − 1 π \pi,F\pi,\ldots,F^{K-1}\pi π , F π , … , F K − 1 π are linearly independent, which excludes equal expected degrees across blocks. Our family sits in the analogue of the excluded regime: with E L = ( E x 1 , 0 ) \mathbb{E}L=(\mathbb{E}x_1,0) E L = ( E x 1 , 0 ) and E [ L L T ] \mathbb{E}[LL^{\mathsf{T}}] E [ L L T ] diagonal, the iterated degree function is T j ( 1 ) ( L ) = x 1 ( E x 1 ) ( E x 1 2 ) j − 1 T^{j}(1)(L)=x_1(\mathbb{E}x_1)(\mathbb{E}x_1^2)^{j-1} T j ( 1 ) ( L ) = x 1 ( E x 1 ) ( E x 1 2 ) j − 1 , so every wheel density is a functional of the radial law alone, constant across the whole slope family.
Elsewhere, RDPG latent laws are identifiable from the full graph law [28 ] , block models generically so [2 ] , and tensor methods recover block parameters from low-order statistics under rank conditions [3 ] . Message-passing neural networks are bounded by the 1-WL test [55 , 38 ] , which on finite graphs is equivalent to tree homomorphism counts [18 , 15 ] and on graphons to tree densities [24 , 10 ] . We use “fiber” as in algebraic statistics, where non-identifiability is a positive-dimensional fiber of the parametrization [17 ] .
Moments and motif counts. Our construction is classical: the truncated Stieltjes problem, Hankel and Jacobi matrices, Gauss–Radau rules [47 , 1 , 20 ] , applied to mixtures since Lindsay (1989). Hankel condition numbers grow exponentially [52 , 7 ] , and point-mass recovery from noisy moments is fragile (Moitra, 2015); determinacy and conditioning come apart, which is the census’s failure. Motif counts are old network summaries [36 , 39 , 45 ] with mature distribution theory [9 , 8 , 35 ] ; we ask what the densities themselves determine.
Model and Main Theorem
Generative model. Fix K ≥ 3 K \ge3 K ≥ 3 and C > 0 C > 0 C > 0 . A configuration is Θ = ( ( w 1 , … , w K ) , ( s 1 , … , s K ) , R ) \Theta= ((w_1,\ldots,w_K),(s_1,\ldots,s_K),R) Θ = (( w 1 , … , w K ) , ( s 1 , … , s K ) , R ) with weights w i > 0 w_i > 0 w i > 0 , w i = w K + 1 − i w_i = w_{K+1-i} w i = w K + 1 − i , ∑ i w i = 1 \sum_i w_i = 1 ∑ i w i = 1 ; slopes s 1 > ⋯ > s K s_1 > \cdots> s_K s 1 > ⋯ > s K with s i = − s K + 1 − i s_i = -s_{K+1-i} s i = − s K + 1 − i (so s k + 1 = 0 s_{k+1}=0 s k + 1 = 0 when K = 2 k + 1 K=2k+1 K = 2 k + 1 ); and a radial law R R R on ( 0 , C ) (0,C) ( 0 , C ) with moments ρ d : = E R [ x d ] \rho_d := \mathbb{E}_R[x^d] ρ d := E R [ x d ] . Each node u u u draws a community c u c_u c u with Pr [ c u = i ] = w i \Pr[c_u=i]=w_i Pr [ c u = i ] = w i and x 1 , u ∼ R x_{1,u}\sim R x 1 , u ∼ R independently, and sets L u = x 1 , u ( 1 , s c u ) L_u=x_{1,u}(1,s_{c_u}) L u = x 1 , u ( 1 , s c u ) . Nodes u , v u,v u , v are joined independently with probability
W ( u , v ) = ⟨ L u , L v ⟩ = x 1 , u x 1 , v ( 1 + s c u s c v ) . (1) W(u,v)=\langle L_u,L_v\rangle=x_{1,u}x_{1,v}(1+s_{c_u}s_{c_v}). \tag*{(1)} W ( u , v ) = ⟨ L u , L v ⟩ = x 1 , u x 1 , v ( 1 + s c u s c v ) . (1)
This is an LSBM with K K K rays through the origin, and a DCSBM with degree parameters x 1 , u x_{1,u} x 1 , u and rank-two connectivity B k l = 1 + s k s l B_{kl}=1+s_ks_l B k l = 1 + s k s l . Writing t i = s i 2 t_i=s_i^2 t i = s i 2 , W ∈ [ 0 , 1 ] W\in[0,1] W ∈ [ 0 , 1 ] for all pairs iff t 1 ≤ T : = min ( 1 , C − 2 − 1 ) t_1\le T:=\min(1,C^{-2}-1) t 1 ≤ T := min ( 1 , C − 2 − 1 ) , which needs C < 1 C<1 C < 1 ; we call such configurations admissible . By reflection symmetry the odd slope moments vanish; m j : = E [ s 2 j ] m_j:=\mathbb{E}[s^{2j}] m j := E [ s 2 j ] are the moments of the squared slope.
The census factorizes. Let t ( F ; Θ ) t(F;\Theta) t ( F ; Θ ) be the homomorphism density of F F F under (1); injective motif counts are unbiased for it (Theorem A.7), and induced (graphlet) densities carry the same information order by order. The census of order m m m , Cen m ( Θ ) \operatorname{Cen}_m(\Theta) Cen m ( Θ ) , collects t ( F ; Θ ) t(F;\Theta) t ( F ; Θ ) over graphs with ∣ V ( F ) ∣ ≤ m |V(F)|\le m ∣ V ( F ) ∣ ≤ m . Call S ⊆ E ( F ) S\subseteq E(F) S ⊆ E ( F ) even if every vertex has even degree in ( V ( F ) , S ) (V(F),S) ( V ( F ) , S ) , and write E ( F ) \mathcal{E}(F) E ( F ) for these sets.
Lemma 3.1 (Factorization and even-subgraph expansion). For every graph F F F ,
t ( F ; Θ ) = ∏ v ∈ V ( F ) ρ deg F v ∑ S ∈ E ( F ) ∏ v ∈ V ( F ) m deg S ( v ) / 2 . t(F;\Theta)=\prod_{v\in V(F)}\rho_{\deg_F v}\sum_{S\in\mathcal{E}(F)}\prod_{v\in V(F)}m_{\deg_S(v)/2}. t ( F ; Θ ) = v ∈ V ( F ) ∏ ρ d e g F v S ∈ E ( F ) ∑ v ∈ V ( F ) ∏ m d e g S ( v ) /2 .
The radii factor out because ∏ u v x u x v = ∏ v x v deg v \prod_{uv}x_ux_v=\prod_v x_v^{\deg v} ∏ uv x u x v = ∏ v x v d e g v ; expanding ∏ u v ( 1 + s u s v ) \prod_{uv}(1+s_us_v) ∏ uv ( 1 + s u s v ) and discarding odd slope moments leaves the even subgraphs, as in the high-temperature expansion of statistical mechanics ([53 ] ) (Theorems A.9 and A.11 ). Forests are therefore blind to the slopes: edge density, degrees, stars and paths depend on R R R alone. A cycle sees 1 + m ℓ 1+m_\ell 1 + m ℓ . What a graph can see is recorded by its slope index h ( F ) : = max S ∈ E ( F ) max v deg S ( v ) / 2 h(F):=\max_{S\in\mathcal{E}(F)}\max_v \deg_S(v)/2 h ( F ) := max S ∈ E ( F ) max v deg S ( v ) /2 , the highest moment in its expansion (Theorem A.13); h ( F ) ≤ ⌊ Δ ( F ) / 2 ⌋ h(F)\le\lfloor\Delta(F)/2\rfloor h ( F ) ≤ ⌊ Δ ( F ) /2 ⌋ , and h ( F ) ≥ j h(F)\ge j h ( F ) ≥ j forces ∣ V ( F ) ∣ ≥ 2 j + 1 |V(F)|\ge2j+1 ∣ V ( F ) ∣ ≥ 2 j + 1 (Theorem A.15). Because every coefficient is nonnegative there is no cancellation, which gives a clean transfer principle.
Proposition 3.2 (Motif transfer). Let Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 share R R R . (i) If m d ( Θ 1 ) = m d ( Θ 2 ) m_d(\Theta_1)=m_d(\Theta_2) m d ( Θ 1 ) = m d ( Θ 2 ) for d ≤ j d\le j d ≤ j , then t ( F ; Θ 1 ) = t ( F ; Θ 2 ) t(F;\Theta_1)=t(F;\Theta_2) t ( F ; Θ 1 ) = t ( F ; Θ 2 ) whenever h ( F ) ≤ j h(F)\le j h ( F ) ≤ j . (ii) If they agree for d < j d<j d < j and m j ( Θ 1 ) > m j ( Θ 2 ) m_j(\Theta_1)>m_j(\Theta_2) m j ( Θ 1 ) > m j ( Θ 2 ) , then t ( F ; Θ 1 ) > t ( F ; Θ 2 ) t(F;\Theta_1)>t(F;\Theta_2) t ( F ; Θ 1 ) > t ( F ; Θ 2 ) whenever h ( F ) = j h(F)=j h ( F ) = j .
This is Theorem A.14 . Motif matching is thus moment matching, graded by h h h ; the question becomes which slope laws share m 0 , … , m K − 2 m_0,\ldots,m_{K-2} m 0 , … , m K − 2 .
Corollary 3.3 (Message passing sees no slope). Configurations sharing R R R have equal densities for every tree. Hence they are indistinguishable by the continuous 1-WL test on graphons, and by every message-passing network without node features, with order-normalized sum aggregation and mean readout, in the graphon limit ([10 ] ); under refinement, every node’s color is a function of its radius alone.
A tree has no nonempty even edge set, so Theorem 3.1 gives t ( T ; Θ ) = ∏ v ρ deg v t(T;\Theta)=\prod_v\rho_{\deg v} t ( T ; Θ ) = ∏ v ρ d e g v . Directly: a node’s degree is x ρ 1 ( 1 + s c E [ s ] ) = x ρ 1 x\rho_1(1+s_c\mathbb{E}[s])=x\rho_1 x ρ 1 ( 1 + s c E [ s ]) = x ρ 1 , and each round of refinement averages the neighbors’ slopes against a mean-zero law (Section A.5). Only E [ s ] = 0 \mathbb{E}[s]=0 E [ s ] = 0 and a community-independent radius are used. Higher-order variants see more, since F K − 1 F_{K-1} F K − 1 has treewidth 2 ([15 ] ), but inherit the suppression of Theorem 5.1.
The fiber. Let K = 2 k K = 2k K = 2 k . From the matched moments form the Hankel matrix M k = ( m a + b − 2 ) a , b ≤ k M_k = (m_{a+b-2})_{a,b\leq k} M k = ( m a + b − 2 ) a , b ≤ k ; its Cholesky factor U U U (M k = U ⊤ U M_k = U^{\top}U M k = U ⊤ U ) gives the Jacobi coefficients a 0 = m 1 , a 1 , … , a k − 2 a_0 = m_1, a_1,\ldots,a_{k-2} a 0 = m 1 , a 1 , … , a k − 2 and b 1 , … , b k − 1 > 0 b_1,\ldots,b_{k-1} > 0 b 1 , … , b k − 1 > 0 , i.e. the three-term recurrence of the monic orthogonal polynomials f j f_j f j of the matched moments (Theorems A.19 and A.22 ). For ξ ∈ R \xi\in\mathbb{R} ξ ∈ R let J ( ξ ) J(\xi) J ( ξ ) be the k × k k \times k k × k tridiagonal matrix with diagonal ( a 0 , … , a k − 2 , ξ ) (a_0,\ldots,a_{k-2},\xi) ( a 0 , … , a k − 2 , ξ ) and off-diagonal ( b 1 , … , b k − 1 ) (b_1,\ldots,b_{k-1}) ( b 1 , … , b k − 1 ) , with eigenvalues t 1 ( ξ ) > ⋯ > t k ( ξ ) t_1(\xi) > \cdots> t_k(\xi) t 1 ( ξ ) > ⋯ > t k ( ξ ) and unit eigenvectors v i v_i v i . The configuration Θ ξ \Theta_\xi Θ ξ has slopes ± t i \pm\sqrt{t_i} ± t i , weights w i = 1 2 ( v i ) 1 2 w_i = \frac{1}{2}(v_i)_1^2 w i = 2 1 ( v i ) 1 2 on each ray of a reflected pair, and radial law R R R . For K = 2 k + 1 K = 2k+1 K = 2 k + 1 the middle ray has slope 0 0 0 , and the same construction is applied to the size-biased moments m d ′ = m d + 1 / m 1 m'_d = m_{d+1}/m_1 m d ′ = m d + 1 / m 1 , giving J ′ ( ξ ) J'(\xi) J ′ ( ξ ) ; the outer rays get weights m 1 ( v i ′ ) 1 2 / ( 2 t i ′ ) m_1(v'_i)_1^2/(2t'_i) m 1 ( v i ′ ) 1 2 / ( 2 t i ′ ) and the middle ray the remainder w k + 1 = 1 − m 1 e 1 ⊤ J ′ ( ξ ) − 1 e 1 w_{k+1} = 1 - m_1\mathbf{e}_1^{\top}J'(\xi)^{-1}\mathbf{e}_1 w k + 1 = 1 − m 1 e 1 ⊤ J ′ ( ξ ) − 1 e 1 (Theorems A.32 and A.35). Write Φ ( Θ ~ ) = { Θ ξ : ξ ∈ ( ξ − , ξ + ] } \Phi(\widetilde{\Theta}) = \{\Theta_\xi: \xi\in(\xi^-,\xi^+]\} Φ ( Θ ) = { Θ ξ : ξ ∈ ( ξ − , ξ + ]} .
Theorem 3.4. Let K ≥ 3 K \geq3 K ≥ 3 , fix R R R , and let Θ ~ \widetilde{\Theta} Θ be admissible with K K K communities.
(a) Fiber. Φ ( Θ ~ ) \Phi(\widetilde{\Theta}) Φ ( Θ ) is exactly the set of admissible K K K -community configurations with radial law R R R whose m 0 , … , m K − 2 m_0,\ldots,m_{K-2} m 0 , … , m K − 2 agree with those of Θ ~ \widetilde{\Theta} Θ . The interval ( ξ − , ξ + ] (\xi^-,\xi^+] ( ξ − , ξ + ] is nondegenerate, and m K − 1 ( Θ ξ ) = σ K ξ + c K m_{K-1}(\Theta_\xi) = \sigma_K\xi+ c_K m K − 1 ( Θ ξ ) = σ K ξ + c K with σ K > 0 \sigma_K > 0 σ K > 0 , so distinct ξ \xi ξ give distinct configurations.
(b) Endpoints. For K = 2 k K = 2k K = 2 k ,
ξ − = − b k − 1 2 f k − 2 ( 0 ) f k − 1 ( 0 ) , ξ + = T − b k − 1 2 f k − 2 ( T ) f k − 1 ( T ) . \xi^- = -b_{k-1}^2\frac{f_{k-2}(0)}{f_{k-1}(0)}, \qquad\xi^+ = T - b_{k-1}^2\frac{f_{k-2}(T)}{f_{k-1}(T)}. ξ − = − b k − 1 2 f k − 1 ( 0 ) f k − 2 ( 0 ) , ξ + = T − b k − 1 2 f k − 1 ( T ) f k − 2 ( T ) . the Gauss–Radau rules of the matched law with a node fixed at 0 0 0 and at T T T ([21 ] ). For K = 2 k + 1 K = 2k+1 K = 2 k + 1 , ξ + \xi^+ ξ + is the same expression in the primed coefficients, and ξ − = ∑ j = 0 k − 1 α j − ∑ j = 0 k − 2 a j ′ \xi^- = \sum_{j=0}^{k-1}\alpha_j-\sum_{j=0}^{k-2}a'_j ξ − = ∑ j = 0 k − 1 α j − ∑ j = 0 k − 2 a j ′ , where α j \alpha_j α j are the recurrence coefficients of the matched law: the k k k -point Gauss rule, at which the middle ray loses its mass.
(c) Matched motifs. t ( F ; ⋅ ) t(F;\cdot) t ( F ; ⋅ ) is constant on Φ ( Θ ~ ) \Phi(\widetilde{\Theta}) Φ ( Θ ) for every F F F with h ( F ) ≤ K − 2 h(F) \leq K-2 h ( F ) ≤ K − 2 : in particular every graph on at most 2 K − 2 2K-2 2 K − 2 vertices, and every graph of maximum degree at most 2 K − 3 2K-3 2 K − 3 , however large.
(d) Breakers. For every F F F with h ( F ) = K − 1 h(F) = K-1 h ( F ) = K − 1 , t ( F ; ⋅ ) t(F;\cdot) t ( F ; ⋅ ) is strictly increasing along the fiber. A graph on 2 K − 1 2K-1 2 K − 1 vertices separates two fiber points iff it has a vertex adjacent to all others whose neighbourhood induces components of even order; among these, the friendship graph F K − 1 F_{K-1} F K − 1 is the unique one with fewest edges. Its density is affine in ξ \xi ξ with slope
ρ 2 K − 2 ρ 2 2 K − 2 m 1 2 K − 2 σ K . \rho_{2K-2}\rho_2^{2K-2}m_1^{2K-2}\sigma_K. ρ 2 K − 2 ρ 2 2 K − 2 m 1 2 K − 2 σ K .
Corollary 3.5 (The census sees exactly the fiber). An admissible K K K -community configuration with radial law R R R agrees with Θ ~ \widetilde{\Theta} Θ on Cen 2 K − 2 \operatorname{Cen}_{2K-2} Cen 2 K − 2 iff it lies in Φ ( Θ ~ ) \Phi(\widetilde{\Theta}) Φ ( Θ ) .
If Θ ∉ Φ ( Θ ~ ) \Theta\notin\Phi(\widetilde{\Theta}) Θ ∈ / Φ ( Θ ) , some m j m_j m j with 1 ≤ j ≤ K − 2 1 \leq j \leq K-2 1 ≤ j ≤ K − 2 differs; at the first such j j j , the friendship graph F j F_j F j (on 2 j + 1 ≤ 2 K − 3 2j+1 \leq2K-3 2 j + 1 ≤ 2 K − 3 vertices, h = j h=j h = j ) separates by Theorem 3.2(ii) (Section A.5).
Corollary 3.6 (No fixed motif order). For every m m m there are K K K and a nondegenerate fiber on which Cen m \operatorname{Cen}_m Cen m is constant (Theorem A.41).
The smallest case. At K = 3 K = 3 K = 3 , J ′ = [ ξ ] J' = [\xi] J ′ = [ ξ ] : the outer rays have squared slope ξ \xi ξ and weight m 1 / ( 2 ξ ) m_1/(2\xi) m 1 / ( 2 ξ ) each, the middle ray weight 1 − m 1 / ξ 1-m_1/\xi 1 − m 1 / ξ , and the fiber is ξ ∈ ( m 1 , T ] \xi\in(m_1,T] ξ ∈ ( m 1 , T ] . The census of order 4 4 4 is constant along it, while m 2 = m 1 ξ m_2 = m_1\xi m 2 = m 1 ξ and the density of the bowtie F 2 F_2 F 2 increase. At ξ ↓ m 1 \xi\downarrow m_1 ξ ↓ m 1 the middle ray empties and the configuration collapses to two rays; at ξ = T \xi= T ξ = T the outer rays reach the admissibility boundary.
Why the corner is free. The Cholesky factor makes the Gram matrix M k \mathbf{M}_k M k of 1 , x , … , x k − 1 1,x,\ldots,x^{k-1} 1 , x , … , x k − 1 orthonormal, and J J J is the shifted-by-one Hankel matrix in that basis (Theorem A.28). The data fill M k \mathbf{M}_k M k completely and its shift everywhere except the bottom-right corner, which is ξ \xi ξ . Any matching configuration yields the same J J J up to its corner (Theorems A.24 and A.27). Since ∂ J / ∂ ξ = e k e k T \partial J/\partial\xi= e_k e_k^{\mathsf{T}} ∂ J / ∂ ξ = e k e k T , every eigenvalue increases with ξ \xi ξ and ∑ i d t i / d ξ = 1 \sum_i dt_i/d\xi= 1 ∑ i d t i / d ξ = 1 (Theorem A.29); by interlacing only t 1 t_1 t 1 can exceed T T T and only t k t_k t k can reach 0, which gives the endpoints (Theorem A.31 ). For odd K K K the middle weight decreases in ξ \xi ξ and diverges to − ∞ -\infty − ∞ as t k ′ ↓ 0 t'_k \downarrow0 t k ′ ↓ 0 , so it vanishes first, at the Gauss rule (Theorem A.37 ). The breaker statements are combinatorial: on 2 K − 1 2K - 1 2 K − 1 vertices, a vertex of S S S -degree 2 K − 2 2K - 2 2 K − 2 must be adjacent to all others, and its neighbours need odd degree inside the neighbourhood, which by the handshake lemma forces even-order components; fewest edges means a perfect matching, i.e. F K − 1 F_{K-1} F K − 1 (Theorems A.17 and A.42 ). The machinery is classical: Krein’s canonical representations ([27 ] ), quasi-orthogonal polynomials ([46 ] ), and Gauss–Radau rules computed by moving the corner ([23 , 21 ] ). The contribution is the reduction of motif matching to this truncated moment problem, and the exhaustive closed-form description it yields.
Geometry of the Fiber at K = 4 K = 4 K = 4
At K = 4 K = 4 K = 4 (k = 2 k = 2 k = 2 ) everything is explicit. With b 1 2 = m 2 − m 1 2 b_1^2 = m_2 - m_1^2 b 1 2 = m 2 − m 1 2 , J ( ξ ) = ( m 1 b 1 b 1 ξ ) J(\xi) = \begin{pmatrix} m_1 & b_1 \\ b_1 & \xi\end{pmatrix} J ( ξ ) = ( m 1 b 1 b 1 ξ ) , the squared-slope law is α 1 δ τ 1 + ( 1 − α 1 ) δ τ 2 \alpha_1\delta_{\tau_1} + (1 - \alpha_1)\delta_{\tau_2} α 1 δ τ 1 + ( 1 − α 1 ) δ τ 2 with τ 1 < τ 2 \tau_1 < \tau_2 τ 1 < τ 2 the eigenvalues, α 1 = ( τ 2 − m 1 ) / ( τ 2 − τ 1 ) \alpha_1 = (\tau_2 - m_1)/(\tau_2 - \tau_1) α 1 = ( τ 2 − m 1 ) / ( τ 2 − τ 1 ) , and ξ − = b 1 2 / m 1 \xi^- = b_1^2/m_1 ξ − = b 1 2 / m 1 , ξ + = T − b 1 2 / ( T − m 1 ) \xi^+ = T - b_1^2/(T - m_1) ξ + = T − b 1 2 / ( T − m 1 ) . We parametrize configurations by θ = ( τ 1 , τ 2 , α 1 ) \theta= (\tau_1,\tau_2,\alpha_1) θ = ( τ 1 , τ 2 , α 1 ) and report position along the fiber as s / a r c s/\mathrm{arc} s / arc , the fraction of arc length—never as ξ \xi ξ , which traverses the curve at non-constant speed. Experiments use the uniform radial law on ( 0 , C ) (0,C) ( 0 , C ) , for which the mean degree is n C 2 / 4 nC^2/4 n C 2 /4 .
Through the configurations of Table 1 (m 1 = 0.21744 m_1 = 0.21744 m 1 = 0.21744 , m 2 = 0.05863 m_2 = 0.05863 m 2 = 0.05863 ) and at C = 0.75 C = 0.75 C = 0.75 (T = 7 / 9 T = 7/9 T = 7/9 ), the fiber has length 1.0571 in θ \theta θ ; its open end has τ 1 → 0 \tau_1 \to0 τ 1 → 0 (α 1 ≈ 0.194 \alpha_1 \approx0.194 α 1 ≈ 0.194 ) and its closed end τ 2 = T \tau_2 = T τ 2 = T (α 1 ≈ 0.965 \alpha_1 \approx0.965 α 1 ≈ 0.965 ); its best-fit plane captures 99.96% of its variance. For C ≤ 1 / 2 C \le1/\sqrt{2} C ≤ 1/ 2 , T = 1 T = 1 T = 1 and the admissible arc extends to length 1.280; we normalize by 1.0571 at every density, and configurations beyond it (s / a r c > 1 s/\mathrm{arc} > 1 s / arc > 1 ) are used only at C ≤ 1 / 2 C \le1/\sqrt{2} C ≤ 1/ 2 . Since α 1 \alpha_1 α 1 rises along the arc, the minority weight w min = min ( α 1 , 1 − α 1 ) w_{\min} = \min(\alpha_1,1 - \alpha_1) w m i n = min ( α 1 , 1 − α 1 ) is two-to-one in position. We name five configurations: LO (w min = 0.211 w_{\min} = 0.211 w m i n = 0.211 ), pair A (0.255) and MID (0.314) on the ascending branch, and HI (0.0375) and pair B (0.036) on the descending branch, where the minority sits on the steep ray.
Table 1. Two configurations on one K = 4 K = 4 K = 4 fiber. The census matches below order 7 exactly; the separator reads a 45% moment gap as 10 − 6 10^{-6} 1 0 − 6 .
The slope laws of pairs A and B differ by 16% of the support range in Wasserstein distance (W 1 = 0.1176 W_1 = 0.1176 W 1 = 0.1176 ): matching low-order densities says little about graphon proximity, as the logarithmic inverse counting lemma predicts.
The Census Route
The suppression in Table 1 is structural, not a poor choice of motif.
Proposition 5.1. In the expansion of Theorem 3.1, every term containing m j m_j m j (j ≥ 1 j \ge1 j ≥ 1 ) is at most m j m 1 2 j m_jm_1^{2j} m j m 1 2 j , and F j F_j F j attains the bound.
A vertex of S S S -degree 2 j 2j 2 j has 2 j 2j 2 j distinct neighbours, each of even S S S -degree at least 2, and m r ≤ m 1 m_r \le m_1 m r ≤ m 1 for r ≥ 1 r \ge1 r ≥ 1 because the squared slopes lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] ; every other factor is at most m 0 = 1 m_0 = 1 m 0 = 1 (Section A.5). The bound is per term; the number of terms carrying m j m_j m j is a fixed combinatorial count of F F F .
So the census reads the first unmatched moment m K − 1 m_{K-1} m K − 1 through m 1 2 ( K − 1 ) ≈ 10 − 4 m_1^{2(K-1)} \approx10^{-4} m 1 2 ( K − 1 ) ≈ 1 0 − 4 at K = 4 K = 4 K = 4 : the best-conditioned census access to m K − 1 m_{K-1} m K − 1 that exists. To measure what this costs without committing to an estimator, we sample 200 graphs from each of two fiber configurations at n ∈ { 2000 , 4000 , 8000 , 16000 , 32000 } n \in\{2000, 4000, 8000, 16000, 32000\} n ∈ { 2000 , 4000 , 8000 , 16000 , 32000 } , estimate t ( F K − 1 ) t(F_{K-1}) t ( F K − 1 ) per graph from homomorphism counts, and form a two-sample z z z -statistic with the empirical across-replicate standard error; the degenerate-map bias of homomorphism counts cancels exactly in this difference (Section B). The standard deviation of the per-graph estimate decays as n − 0.49 n^{-0.49} n − 0.49 , as latent sampling predicts, and we extrapolate it to the n ∗ n^* n ∗ at which ∣ Δ ∣ / S E = 2.8 |\Delta|/\mathrm{SE} = 2.8 ∣Δ∣/ SE = 2.8 (power 0.8 at two-sided α = 0.05 \alpha= 0.05 α = 0.05 ; Table 2 ). Across four fitting windows n ∗ n^* n ∗ at K = 4 K = 4 K = 4 ranges over 2.7 × 10 12 2.7 \times10^{12} 2.7 × 1 0 12 –9.7 × 10 12 9.7 \times10^{12} 9.7 × 1 0 12 , so we quote an order. These figures pool 200 graphs per configuration; with one graph per configuration n ∗ n^* n ∗ rises about 200-fold, to roughly 2 × 10 15 2 \times10^{15} 2 × 1 0 15 at K = 4 K = 4 K = 4 . The extrapolation assumes the n − 1 / 2 n^{-1/2} n − 1/2 decay of a nondegenerate U U U -statistic persists; the graphs stay dense as n n n grows, so no sparse-graph transition intervenes. There is no direct detection at any K K K or n n n . Without extrapolating, the perturbation needed for a detectable effect is about 100× larger through the census than through the spectrum (78× at n = 2000 n = 2000 n = 2000 , 123× at n = 32,000 n = 32{,}000 n = 32 , 000 ). Sparsity does not help: for a scale family of radial laws ρ d ∝ C d \rho_d \propto C^d ρ d ∝ C d , so by Theorem 3.1 the relative separation is exactly invariant to C C C , and the measured floor-to-signal ratio is flat to within 1.4× from C = 0.75 C = 0.75 C = 0.75 to 0.05.
Table 2. Census route by K K K (threshold order 2 K − 1 2K - 1 2 K − 1 ): moment and density separation along the fiber, and the extrapolated n ∗ n^* n ∗ with 200 graphs or one graph per configuration.
The moment inversion the theory suggests (m 2 , m 3 m_2,m_3 m 2 , m 3 from t ( F 2 ) t(F_2) t ( F 2 ) , t ( F 3 ) t(F_3) t ( F 3 ) , then Prony) produced no valid slope law in any of 12,600 replicates: dividing by m 1 4 m_1^4 m 1 4 and m 1 6 m_1^6 m 1 6 amplifies noise 447× and 9,461×. A constrained variant returns valid fits, all on the boundary of the admissible set and displaced by up to 72% of the arc (Section B).
No Information Barrier
The census cannot separate points of the fiber; the graph can. At the population level, the law of an RDPG determines the distribution of latent positions up to an orthogonal transformation ([28 ] ). Here E L = ( ρ 1 , 0 ) EL = (\rho_1, 0) E L = ( ρ 1 , 0 ) pins it to the reflection x 2 ↦ − x 2 x_2 \mapsto-x_2 x 2 ↦ − x 2 , which maps the symmetric family to itself, so distinct fiber points induce distinct graph laws.
At finite n n n , model-based fits recover the position along the fiber from the observed graph alone: RayEM to within 1% of the arc and the LSBM authors’ sampler to within 2.3%, at every cell tested (§ 7 , Table 3 ). As a check that involves no estimation, the held-out log-loss with the true latent positions snapped to each candidate’s rays picks the generating configuration in all 36 cells (K = 4 , 5 , 6 K = 4, 5, 6 K = 4 , 5 , 6 , down to mean degree 5), and its margin matches the analytic population log-loss gap at ratios 0.93–1.04 (Section C). The obstruction belongs to the census, not to the graph.
Table 3. Median total error ∣ θ ^ − θ 0 ∣ |\hat{\theta}-\theta_0| ∣ θ ^ − θ 0 ∣ , % of arc, R = 200 R=200 R = 200 (mean degree in parentheses), and fitted-to-true minority weight at HI. SCORE at LO is bimodal. † ^{\dagger} † Along-fiber RMSE over all R = 20 R=20 R = 20 chains.
The Spectral Pipeline
Estimators. P1-cluster is the embed-then-cluster pipeline in its simplest form: the two-dimensional ASE with an observable-only canonicalization, a per-node slope T ^ = x ^ 2 / x ^ 1 \widehat{T} = \widehat{x}_2/\widehat{x}_1 T = x 2 / x 1 (in d = 2 d = 2 d = 2 , SCORE’s eigenvector ratio up to a constant), a small-radius filter, and one-dimensional 2-means on ∣ T ^ ∣ \lvert\widehat{T}\rvert ∣ T ∣ ; atoms are cluster means of T ^ 2 \widehat{T}^{2} T 2 and the weight is the cluster proportion. P1-Prony , the classical moment-matching alternative, applies Prony’s method to the first three moments of T ^ 2 \widehat{T}^{2} T 2 . Both are handed K K K , d d d and the reflection symmetry.
Bias, not spread. At C = 0.3 C = 0.3 C = 0.3 , n = 32,000 n = 32{,}000 n = 32 , 000 (mean degree 720) P1-cluster lands 33× closer to the fiber than to the truth; all 200 replicates lie within 0.02 of it in θ \theta θ (1.9% of the arc) while displaced along it (Figure 1 ). The displacement is bias, 7–15 times the spread at the named configurations (Table 5 ) and 5–14 times across all on-curve cells displaced by at least 5% (Section H). The estimate is precise, on the curve, and wrong. It is not an implementation error: the same code recovers α 1 \alpha_1 α 1 to 0.5% at C = 0.75 C = 0.75 C = 0.75 , and other initializations leave HI at 29.9–31.4%.
Figure 1. P1-cluster at configuration HI (w min = 0.0375 w_{\min} = 0.0375 w m i n = 0.0375 ), n = 32,000 n = 32{,}000 n = 32 , 000 . Top: the fiber and estimates in the fiber’s best-fit plane at two densities. Bottom: the same estimates in intrinsic coordinates (position along the fiber versus signed distance across it). At mean degree 720 every estimate lies close to the curve yet is displaced 31% of the arc along it.
Table 5. P1-cluster at C = 0.3 C = 0.3 C = 0.3 , n = 32,000 n = 32{,}000 n = 32 , 000 : intrinsic signed along-fiber displacement (bias) and spread, % of arc (+ toward the pair-B end).
Why the census fiber. At K = 4 K=4 K = 4 the census fiber is exactly the level set of ( m 1 , m 2 ) (m_1,m_2) ( m 1 , m 2 ) (Theorem 3.4 (a)), so “on the fiber, displaced along it” could be read as “m ^ 1 , m ^ 2 \hat{m}_1,\hat{m}_2 m ^ 1 , m ^ 2 accurate, m ^ 3 \hat{m}_3 m ^ 3 not”. That reading is the point rather than an objection: the theorem says this level set is all that low-order statistics determine, and any estimator that fits the low moments well but the next one poorly inherits it. What the theorem adds is the set’s geometry, a curve with known endpoints and length, which makes the displacement measurable and bounded. The error follows that curve, not a fixed ill-conditioned direction: the mean error tracks the local tangent to within 16 16 16 –24 ∘ 24^\circ 2 4 ∘ at five configurations whose tangents differ by up to 75 ∘ 75^\circ 7 5 ∘ ; moving the truth off the fiber destroys the alignment (15.7 ∘ 15.7^\circ 15. 7 ∘ on it, 66.5 ∘ 66.5^\circ 66. 5 ∘ at offset 0.35 0.35 0.35 ); and RayEM, fitted to the same embedding, is not displaced.
Two tilts, one amplifier. A flat direction alone produces wide unbiased scatter; displacement also needs a tilt, a systematic estimator error, which the fiber amplifies because across it the objective climbs and along it nothing resists. For P1-cluster the tilt is a partition error: the fitted minority weight is inflated 1.11 × 1.11\times 1.11 × at balanced weights and 4.4 × 4.4\times 4.4 × at w min = 0.0375 w_{\min}=0.0375 w m i n = 0.0375 . For P1-Prony it is a moment error: ASE noise inflates m ^ 3 \hat{m}_3 m ^ 3 by 40 40 40 –64 % 64\% 64% , and the displacement is toward larger m 3 m_3 m 3 in 229 of 276 cells. Both are second-order ASE bias (E S ^ = m 1 + σ 2 \mathbb{E}\hat{S}=m_1+\sigma^2 E S ^ = m 1 + σ 2 , σ 2 = O ( n − 1 ) \sigma^2=O(n^{-1}) σ 2 = O ( n − 1 ) ; Section D).
Published pipelines. We ran three published DCSBM pipelines on the same embeddings, reading parameters off their clusters with one shared plug-in (Section E): row-normalized spectral clustering (Qin and Rohe, [40 ] ; Lei and Rinaldo, [29 ] ), spherical coordinates with a Gaussian mixture (Sanna Passino et al., [44 ] ), and SCORE (Jin, [25 ] ). Table 3 reports total error. The first two slide along the fiber where the minority sits on the steep ray, by up to 58% of the arc, with the minority weight inflated 4–13× \times × . SCORE avoids the slide there but fails bimodally at LO, near the fiber’s endpoint: at C = 0.5 C=0.5 C = 0.5 , 35% of its replicates land about 105% of the arc away. Adding P1’s small-radius filter to SCORE restores the slide. In a factorial of features (ratio, angle, unit vector), clusters (k k k -means, GMM) and the filter, no variant keeps total error below 5% of the arc at every cell (Section E). Three predictions we registered about which component matters failed (Section G), so we claim the pattern, not a mechanism.
What avoids it. Model-based fits, which are given the ray family and keep the embedding’s noise model, are accurate at every cell. RayEM is a ray-constrained instance of Gaussian mixture modeling of ASE rows under their central-limit covariance (Athreya et al., [4 ] ; Rubin-Delanchy et al., 2022), fitted by EM (Section F). Its total error is below 1% of the arc everywhere tested, and the fitted minority weight is unbiased. The LSBM authors’ Bayesian sampler [44 ] , with curves restricted to lines through the origin, lands within 0.3% and 1.8% of the arc at the two cells we ran. RayEM’s objective is not flat along the fiber: its fit beats the truth by a median of 0.9–1.6 units, the size ordinary noise produces (1 2 χ 3 2 ≈ 1.2 \frac{1}{2}\chi^2_3 \approx1.2 2 1 χ 3 2 ≈ 1.2 ). The same embedding, read through two kinds of statistic, is displaced along the fiber or not; the displacement is a property of the summary, not of the embedding. We have not separated the contribution of the noise model from that of the ray family.
Regime Map and Practitioner Guidance
Displacement rises monotonically as the minority weight falls and fades with density (Figure 2 ): at C = 0.3 C = 0.3 C = 0.3 , n = 32,000 n = 32{,}000 n = 32 , 000 it grows from 0.19% at w min = 0.495 w_{\min} = 0.495 w m i n = 0.495 to 45.5% at w min = 0.03 w_{\min} = 0.03 w m i n = 0.03 . Three regimes appear. For n n n too small the error is large, off the curve, and roughly isotropic; the estimator is visibly bad. In an intermediate regime the error collapses onto the fiber, with at least 80% of replicates within 0.02 of it, and is displaced by up to 54% of the arc at 5–14 times its spread. For n n n large enough the displacement clears. At HI it runs 48.8% → 7.5% → 0.24% as n n n grows from 2000 to 32,000 at C = 0.75 C = 0.75 C = 0.75 , and 55.4% → 44.6% → 2.6% at C = 0.5 C = 0.5 C = 0.5 ; at C = 0.3 C = 0.3 C = 0.3 it has not cleared by n = 32,000 n = 32{,}000 n = 32 , 000 (31.4%). The clearing threshold rises as density falls.
Figure 2. Intrinsic along-fiber displacement of P1-cluster over 276 cells (9 density levels; up to 21 steep-ray and 10 shallow-ray configurations). Left: minority on the steep ray; right: on the shallow ray, where w min ≥ 0.19 w_{\min} \ge0.19 w m i n ≥ 0.19 . The safe region is top right. The hatched row (mean degree 45) is estimator breakdown (off-curve error).
Check 1: am I in the regime? Look up displacement against mean degree, fitted minority weight, and which ray carries the minority. Because the fitted minority weight is itself inflated (1.11× at balanced weights, 4.67× at pair B), thresholds read off the true weight under-warn, and we state them on the fitted scale (Table 8 in Section H; K = 4 K = 4 K = 4 , uniform radial law). Displacement stays under 5% at every weight at mean degree 2000 and above; with the minority on the steep ray, a fitted weight of at least 0.095 is needed at mean degree 1125, 0.37 at 720, and 0.42 at 500.
Table 8: Largest along-fiber displacement and safe region, per estimator, branch and ( C , n ) (C,n) ( C , n ) . Displacement is intrinsic and signed (% of the reference arc; + toward the pair-B end), with the relative change in m 3 m_3 m 3 at the landing point. Safe means ∣ d i s p l a c e m e n t ∣ < 5 % |\mathrm{displacement}| < 5\% ∣ displacement ∣ < 5% for this and every larger minority weight on the same branch, stated on the true and on the fitted weight scale; “none means no safe weight on that branch. unsafe of : unsafe points out of points on the branch. Mean degree 45 is estimator breakdown (off-curve error) and is not comparable to the other rows.
Table 8.
Check 2: what to run instead. Fit the embedding with a model that keeps its noise geometry rather than summarizing each node by a direction. RayEM and the Bayesian LSBM are accurate to within 1% and 2.3% of the arc at every cell tested, including the cells where every summary pipeline fails (Table 3 ). They need K K K and the ray family; their behavior when these are wrong is untested (§ 9 ).
Check 3: why my confidence region is silent. Nominal 95% regions built from sampling variability miss the truth at every configuration in 17 of 18 (estimator, C C C , n n n ) groups, and contain it at 5.1% in the best, even using the true replicate covariance. The error is bias in every direction; the across-fiber offset alone is 1.5–33 times its own spread. Bootstrap, jackknife, sandwich and profile methods all estimate variance and assume asymptotic unbiasedness, so none can bridge it. Nor does the natural single-graph remedy: subsampling one graph and extrapolating in n n n flags low density rather than displacement, and Richardson-correcting the estimates overshoots where the bias is small (Section G).
Check 4: how wide is the ambiguity? The fiber of Theorem 3.4 through the fit’s own ( m ^ 1 , m ^ 2 ) (\hat{m}_1,\hat{m}_2) ( m ^ 1 , m ^ 2 ) needs no solver at K = 4 K = 4 K = 4 and shows how much the low-order summary leaves open: a fit giving minority weight 0.17 may sit on a fiber spanning 0.03 to 0.50. Read it as a width, not a confidence set; it contains the truth reliably only in the densest cells (Table 9 in Section H).
Table 9. Coverage of the fitted ambiguity set (the fiber through the fit’s own ( m ^ 1 , m ^ 2 ) (\hat{m}_1,\hat{m}_2) ( m ^ 1 , m ^ 2 ) ) at a tolerance of 1% of the arc, against the point estimate and a χ 3 2 \chi^2_3 χ 3 2 95% ellipsoid built from the true replicate covariance. Coverage is measured, not guaranteed.
Scope and Discussion
The shared radial law is load-bearing: it factors out of every density (Theorem 3.1) and reduces the census to a truncated moment problem. The fiber nonetheless transfers upward: configurations agreeing below order 2 K − 1 2K - 1 2 K − 1 still agree in the larger family where each ray has its own radial scale, since enlarging a model class can only add non-identifiability, and a practitioner cannot impose the restriction on data. What does not transfer is the closed form; relaxing the symmetry adds parameters and census constraints, and which grows faster is unproved.
Limitations. The theory covers the symmetric family with a shared radial law; the spectral experiments are at K = 4 K = 4 K = 4 , n ≤ 32,000 n \le32{,}000 n ≤ 32 , 000 , on one fiber, on simulated graphs. The census cost n ∗ n^* n ∗ is extrapolated (Table 2 ). The message-passing result is a graphon-limit statement for networks without node features; spectral positional encodings do carry the slopes. Every estimator is given K K K , the model-based fits also the ray family; we do not study selecting K K K , noting only that the census cannot separate K K K from K − 1 K - 1 K − 1 at the fiber’s open end, where two rays merge or the middle ray empties (Theorems A.31 and A.37 ). Higher-order entrywise bias correction ([54 ] ) might reduce the tilt of summary pipelines; we have not tested it.
Use of Generative AI
In this work, we used generative AI tools for formulating precise mathematical claims consistent with the standard terminology used in the literature, writing the proof and double-checking notations and consistencies in the proof, identifying gaps in the proof, designing and providing feedback for the suite of experiments as well as suggesting additional ablations, helping analyze the results and identifying bugs in the code that produced such results, assisting with the interpretation of results (final interpretations are the authors’), writing the test drivers and plotting routines, implementing the comparison estimators (RayEM and the published spectral pipelines) from author-approved designs, and identifying typos and non-material algebraic errors in the proof. We have not used generative AI tools for supplying the main mathematical ideas of the proof (the main theorem and its key mathematical ideas belong to the authors; some secondary results, Corollaries 3.3 and 3.5, Proposition 5.1 and Corollary A.38 , were proposed or proved with AI assistance and verified by the authors), or for main coding tasks such as the inference engine. Tasks such as cleaning and reformatting datasets and assisting with translation are not applicable to this work.
We also used generative AI tools to create plotting and graphing code from experimental results, suggest the suites of experiments and the range of parameters to run them over, draft major parts of the paper, correct grammar and style, search the literature for related work, summarize related papers, compare our paper with them so as not to overclaim novelty, and brainstorm further experiments in light of that work.
We have reviewed all AI-assisted work and take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI.
Proofs
Moments and motif density
We call two graphs that are generated from two different configurations “similar” if the expected density of many subgraphs are the same. This is a loose term, but in the next few sections we will revisit more precisely which subgraph densities are matched and the smallest subgraph whose density can tell them apart, along with the characteristics of these configurations. For now, we would like to establish the link between subgraph densities and slope moments.
The link is developed in Sections A.1.2–A.1.5. The density of a motif F F F factors into a radial part, which depends only on R R R , and a slope part (Lemma A.9). The slope part is a polynomial with nonnegative coefficients in the even slope moments m 1 , m 2 , … m_1,m_2,\ldots m 1 , m 2 , … , indexed by the even subgraphs of F F F (Theorem A.11). The highest moment index that appears is a purely combinatorial invariant of F F F , its slope index h ( F ) h(F) h ( F ) (Definition A.13). Consequently, configurations that share R R R and match slope moments up to m j m_j m j have identical densities for every motif on at most 2 j + 2 2j+2 2 j + 2 vertices, and if they differ first at m j + 1 m_{j+1} m j + 1 they are separated on 2 j + 3 2j+3 2 j + 3 vertices, first by the friendship graph F j + 1 F_{j+1} F j + 1 (Corollary A.18).
Slope Moments
So now the immediate problem is, given a configuration, what other configurations can match its lower moments, and at which higher moments are they broken?
A few consequences of the generative model are immediate.
Proposition A.1. Let μ j \mu_j μ j be the j j j -th moment of the slope: μ j : = E [ s j ] \mu_j := \mathbb{E}[s^j] μ j := E [ s j ] . Then μ j = 0 \mu_j=0 μ j = 0 if j j j is odd and positive if j j j is even. We write m j : = μ 2 j m_j := \mu_{2j} m j := μ 2 j .
Proof. The slope law is symmetric, since s i = − s K + 1 − i s_i=-s_{K+1-i} s i = − s K + 1 − i and w i = w K + 1 − i w_i=w_{K+1-i} w i = w K + 1 − i , so the odd moments vanish. For even j j j , μ j = ∑ i w i s i j > 0 \mu_j=\sum_i w_i s_i^j>0 μ j = ∑ i w i s i j > 0 because the weights are positive and some slope is nonzero. □ \square □
Definition A.2. Let M j \mathrm{M}_j M j be a j × j j \times j j × j matrix that contains the even moments of the slope (or, moments of the squared slope). That is, M a , b = m ( a − 1 ) + ( b − 1 ) \mathrm{M}_{a,b}=m_{(a-1)+(b-1)} M a , b = m ( a − 1 ) + ( b − 1 ) , 1 ≤ a , b ≤ j 1\leq a,b\leq j 1 ≤ a , b ≤ j . So the top-left corner of M j \mathrm{M}_j M j is always 1 1 1 . Let D j : = det ( M j ) D_j:=\det(\mathrm{M}_j) D j := det ( M j ) .
We can see that M \mathrm{M} M is constant along any anti-diagonal and contains the moments of s s s from zero all the way up to m 2 j − 2 m_{2j-2} m 2 j − 2 (the 4 j − 4 4j-4 4 j − 4 -th moment). Given two configuration Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 we would like to characterize how much of the entries of M \mathrm{M} M are matching.
Definition A.3 (Perfect matching of order j j j ). Configurations Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 are perfectly matching of order j j j , written Θ 1 ∼ j Θ 2 \Theta_1\sim_j\Theta_2 Θ 1 ∼ j Θ 2 , if
m d ( Θ 1 ) = m d ( Θ 2 ) ∀ 0 ≤ d ≤ j m_d(\Theta_1)=m_d(\Theta_2)\quad\forall\,0\leq d\leq j m d ( Θ 1 ) = m d ( Θ 2 ) ∀ 0 ≤ d ≤ j Equivalently μ e ( Θ 1 ) = μ e ( Θ 2 ) \mu_e(\Theta_1)=\mu_e(\Theta_2) μ e ( Θ 1 ) = μ e ( Θ 2 ) for all e ≤ 2 j e\leq2j e ≤ 2 j .
Definition A.4 (Near perfect matching of order j j j ). Configurations Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 are nearly perfectly matching of order j j j , written Θ 1 ∼ j ∘ Θ 2 \Theta_1\sim_j^{\circ}\Theta_2 Θ 1 ∼ j ∘ Θ 2 , if all the equalities of Definition A.3 hold, except possibly the one for the top monomial m j = μ 2 j m_j=\mu_{2j} m j = μ 2 j .
Note that near perfect matching does not require the m j m_j m j to be different, it just does not require them to be the same. Therefore, both ∼ j \sim_j ∼ j and ∼ j ∘ \sim_j^{\circ} ∼ j ∘ are equivalence relations (reflexive, symmetric, and transitive), and ∼ j \sim_j ∼ j implies ∼ j ∘ \sim_j^{\circ} ∼ j ∘ .
Definition A.5 (Matching Order). Let ord ( Θ 1 , Θ 2 ) : = max { j : Θ 1 ∼ j Θ 2 } \operatorname{ord}(\Theta_1,\Theta_2):=\max\{j:\Theta_1\sim_j\Theta_2\} ord ( Θ 1 , Θ 2 ) := max { j : Θ 1 ∼ j Θ 2 } . That is, the maximum order such that both configurations match perfectly.
Homomorphism densities of the model
Throughout, F = ( V ( F ) , E ( F ) ) F=(V(F),E(F)) F = ( V ( F ) , E ( F )) is a finite simple graph and deg F ( v ) \deg_F(v) deg F ( v ) is the degree of v v v in F F F . Write π Θ : = ∑ i w i δ s i \pi_\Theta:=\sum_i w_i\delta_{s_i} π Θ := ∑ i w i δ s i for the slope law of Θ \Theta Θ , so that μ j = E s ∼ π Θ [ s j ] \mu_j=\mathbb{E}_{s\sim\pi_\Theta}[s^j] μ j = E s ∼ π Θ [ s j ] . Write
ρ d : = E x ∼ R [ x d ] , d ≥ 0 \rho_d:=\mathbb{E}_{x\sim R}[x^d],\qquad d\geq0 ρ d := E x ∼ R [ x d ] , d ≥ 0
for the radial moments . Since R R R is supported on ( 0 , C ) (0,C) ( 0 , C ) , every ρ d \rho_d ρ d is finite and positive.
The model of Section 3 is a graphon in the sense of Lovász [32 ] . Its latent space is Ω = [ K ] × ( 0 , C ) \Omega=[K]\times(0,C) Ω = [ K ] × ( 0 , C ) with probability measure P = π Θ ⊗ R P=\pi_\Theta\otimes R P = π Θ ⊗ R , where we identify community c c c with slope s c s_c s c , and its kernel is
W ( ( c , x ) , ( c ′ , x ′ ) ) = x x ′ ( 1 + s c s c ′ ) . W\bigl((c,x),(c',x')\bigr)=xx'(1+s_cs_{c'}). W ( ( c , x ) , ( c ′ , x ′ ) ) = x x ′ ( 1 + s c s c ′ ) .
Definition A.6 (Homomorphism density). The homomorphism density of F F F under Θ \Theta Θ is
t ( F ; Θ ) : = ∫ Ω V ( F ) ∏ u v ∈ E ( F ) W ( z u , z v ) ∏ v ∈ V ( F ) d P ( z v ) . t(F;\Theta):=\int_{\Omega^{V(F)}}\prod_{uv\in E(F)}W(z_u,z_v)\prod_{v\in V(F)}dP(z_v). t ( F ; Θ ) := ∫ Ω V ( F ) uv ∈ E ( F ) ∏ W ( z u , z v ) v ∈ V ( F ) ∏ d P ( z v ) .
This is the population quantity that motif counts estimate. Let G n G_n G n be a graph on n ≥ ∣ V ( F ) ∣ n\geq|V(F)| n ≥ ∣ V ( F ) ∣ nodes generated from Θ \Theta Θ , and let t i n j ( F , G n ) t_{\mathrm{inj}}(F,G_n) t inj ( F , G n ) be the number of injective homomorphisms F → G n F\to G_n F → G n divided by n ( n − 1 ) ⋯ ( n − ∣ V ( F ) ∣ + 1 ) n(n-1)\cdots(n-|V(F)|+1) n ( n − 1 ) ⋯ ( n − ∣ V ( F ) ∣ + 1 ) .
Proposition A.7 (Motif counts are unbiased for t t t ). E [ t i n j ( F , G n ) ] = t ( F ; Θ ) \mathbb{E}[t_{\mathrm{inj}}(F,G_n)]=t(F;\Theta) E [ t inj ( F , G n )] = t ( F ; Θ ) .
Proof. Fix an injective map ϕ : V ( F ) → [ n ] \phi:V(F)\to[n] ϕ : V ( F ) → [ n ] . The latent vectors ( c ϕ ( v ) , x ϕ ( v ) ) , v ∈ V ( F ) (c_{\phi(v)},x_{\phi(v)}),\,v\in V(F) ( c ϕ ( v ) , x ϕ ( v ) ) , v ∈ V ( F ) , are i.i.d. with law P P P , because ϕ \phi ϕ is injective. Conditional on the latents, the edges ϕ ( u ) ϕ ( v ) \phi(u)\phi(v) ϕ ( u ) ϕ ( v ) , u v ∈ E ( F ) uv\in E(F) uv ∈ E ( F ) , are distinct node pairs and therefore independent, with probabilities W W W . So the probability that ϕ \phi ϕ is a homomorphism is t ( F ; Θ ) t(F;\Theta) t ( F ; Θ ) . Average over ϕ \phi ϕ . □ \square □
Concentration of t i n j ( F , G n ) t_{\mathrm{inj}}(F,G_n) t inj ( F , G n ) around its mean as n → ∞ n\to\infty n → ∞ is standard [32 ] . We therefore identify the “census” with the population densities.
Definition A.8 (Census of order $m). Cen m ( Θ ) : = ( t ( F ; Θ ) ) F : ∣ V ( F ) ∣ ≤ m \operatorname{Cen}_m(\Theta):=(t(F;\Theta))_{F:|V(F)|\leq m} Cen m ( Θ ) := ( t ( F ; Θ ) ) F : ∣ V ( F ) ∣ ≤ m .
Remark. Induced (graphlet) densities carry the same information as homomorphism densities at each order. For F F F on vertex set V V V with ∣ V ∣ = m |V|=m ∣ V ∣ = m , the injective density is a sum of induced densities, t i n j ( F ) = ∑ F ′ ⊇ F t i n d ( F ′ ) t_{\mathrm{inj}}(F)=\sum_{F'\supseteq F}t_{\mathrm{ind}}(F') t inj ( F ) = ∑ F ′ ⊇ F t ind ( F ′ ) , over graphs F ′ F' F ′ on the same vertex set V V V containing F F F . Möbius inversion gives t i n d ( F ) = ∑ F ′ ⊇ F ( − 1 ) ∣ E ( F ′ ) ∣ − ∣ E ( F ) ∣ t i n j ( F ′ ) t_{\mathrm{ind}}(F)=\sum_{F'\supseteq F}(-1)^{|E(F')|-|E(F)|}t_{\mathrm{inj}}(F') t ind ( F ) = ∑ F ′ ⊇ F ( − 1 ) ∣ E ( F ′ ) ∣ − ∣ E ( F ) ∣ t inj ( F ′ ) . Hence two configurations agree on all induced densities of order m m m if and only if they agree on all homomorphism densities of graphs on exactly m m m vertices. Graphlet counts (e.g. ORCA) are thus covered by Cen m \operatorname{Cen}_m Cen m .
Lemma A.9 (Radial–slope factorization).
t ( F ; Θ ) = ( ∏ v ∈ V ( F ) ρ deg F ( v ) ) ⋅ τ ( F ; π Θ ) , τ ( F ; π ) : = E [ ∏ u v ∈ E ( F ) ( 1 + s u s v ) ] . t(F;\Theta)=\left(\prod_{v\in V(F)}\rho_{\deg_F(v)}\right)\cdot\tau(F;\pi_\Theta),\qquad\tau(F;\pi):=\mathbb{E}\left[\prod_{uv\in E(F)}(1+s_us_v)\right]. t ( F ; Θ ) = v ∈ V ( F ) ∏ ρ d e g F ( v ) ⋅ τ ( F ; π Θ ) , τ ( F ; π ) := E uv ∈ E ( F ) ∏ ( 1 + s u s v ) . where ( s v ) v ∈ V ( F ) (s_v)_{v\in V(F)} ( s v ) v ∈ V ( F ) are i.i.d. with law π \pi π .
Proof. ∏ u v ∈ E ( F ) x u x v = ∏ v x v deg F ( v ) \prod_{uv\in E(F)}x_ux_v=\prod_vx_v^{\deg_F(v)} ∏ uv ∈ E ( F ) x u x v = ∏ v x v d e g F ( v ) . The radii are independent of the slopes and of each other, so the expectation splits. □ \square □
Remark. The fiber constructions of Sections A.2 and A.3 vary only ( w , s ) (w,s) ( w , s ) and keep R R R fixed. Since every ρ d > 0 \rho_d>0 ρ d > 0 , two configurations sharing R R R have t ( F ; Θ 1 ) = t ( F ; Θ 2 ) t(F;\Theta_1)=t(F;\Theta_2) t ( F ; Θ 1 ) = t ( F ; Θ 2 ) if and only if τ ( F ; π Θ 1 ) = τ ( F ; π Θ 2 ) \tau(F;\pi_{\Theta_1})=\tau(F;\pi_{\Theta_2}) τ ( F ; π Θ 1 ) = τ ( F ; π Θ 2 ) , and the signs of the differences agree. R R R enters the slope problem only through the admissibility threshold T T T (Section A.2.2).
Even-subgraph expansion
Definition A.10 (Even subgraphs). A set S ⊆ E ( F ) S \subseteq E(F) S ⊆ E ( F ) is even if every vertex of F F F has even degree in the spanning subgraph ( V ( F ) , S ) (V(F), S) ( V ( F ) , S ) . Write deg S ( v ) \operatorname{deg}_{S}(v) deg S ( v ) for that degree and E ( F ) \mathcal{E}(F) E ( F ) for the set of even subsets. E ( F ) \mathcal{E}(F) E ( F ) contains ∅ \varnothing ∅ and is the cycle space of F F F over GF ( 2 ) \operatorname{GF}(2) GF ( 2 ) .
Theorem A.11 (Even-subgraph expansion).
τ ( F ; π Θ ) = ∑ S ∈ E ( F ) ∏ v ∈ V ( F ) m deg S ( v ) / 2 . \tau(F; \pi_{\Theta}) = \sum_{S \in\mathcal{E}(F)} \prod_{v \in V(F)} m_{\operatorname{deg}_{S}(v)/2}. τ ( F ; π Θ ) = S ∈ E ( F ) ∑ v ∈ V ( F ) ∏ m deg S ( v ) /2 . Proof. Expand the product: ∏ u v ∈ E ( F ) ( 1 + s u s v ) = ∑ S ⊆ E ( F ) ∏ u v ∈ S s u s v = ∑ S ⊆ E ( F ) ∏ v s v deg S ( v ) \prod_{uv \in E(F)}(1+s_{u}s_{v}) = \sum_{S \subseteq E(F)} \prod_{uv \in S}s_{u}s_{v} = \sum_{S \subseteq E(F)} \prod_{v} s_{v}^{\operatorname{deg}_{S}(v)} ∏ uv ∈ E ( F ) ( 1 + s u s v ) = ∑ S ⊆ E ( F ) ∏ uv ∈ S s u s v = ∑ S ⊆ E ( F ) ∏ v s v deg S ( v ) . Take expectations using independence: the term for S S S equals ∏ v μ deg S ( v ) \prod_{v}\mu_{\operatorname{deg}_{S}(v)} ∏ v μ deg S ( v ) . By Proposition A.1 (odd slope moments vanish), the term is zero unless every deg S ( v ) \operatorname{deg}_{S}(v) deg S ( v ) is even, i.e. S ∈ E ( F ) S \in\mathcal{E}(F) S ∈ E ( F ) . For even S S S , μ deg S ( v ) = m deg S ( v ) / 2 \mu_{\operatorname{deg}_{S}(v)} = m_{\operatorname{deg}_{S}(v)/2} μ deg S ( v ) = m deg S ( v ) /2 , and m 0 = 1 m_{0}=1 m 0 = 1 for vertices not touched by S S S .
Example A.12. Forests have E ( F ) = { ∅ } \mathcal{E}(F)=\{\varnothing\} E ( F ) = { ∅ } , so τ = 1 \tau=1 τ = 1 and t ( F ; Θ ) = ∏ v ρ deg F ( v ) t(F;\Theta)=\prod_{v}\rho_{\operatorname{deg}_{F}(v)} t ( F ; Θ ) = ∏ v ρ deg F ( v ) : tree densities (edge density, degree distribution, stars, paths) depend on R R R only and are blind to the slopes. The cycle C ℓ C_{\ell} C ℓ has E = { ∅ , E ( C ℓ ) } \mathcal{E}=\{\varnothing,E(C_{\ell})\} E = { ∅ , E ( C ℓ )} , so τ ( C ℓ ) = 1 + m 1 ℓ \tau(C_{\ell})=1+m_{1}^{\ell} τ ( C ℓ ) = 1 + m 1 ℓ ; in particular t ( t r i a n g l e ) = ρ 2 3 ( 1 + m 3 1 ) t(\mathrm{triangle})=\rho_{2}^{3}(1+m_{3}^{1}) t ( triangle ) = ρ 2 3 ( 1 + m 3 1 ) .
Definition A.13 (Slope index).
h ( F ) : = max S ∈ E ( F ) max v ∈ V ( F ) deg S ( v ) 2 . h(F) := \max_{S \in\mathcal{E}(F)} \max_{v \in V(F)} \frac{\operatorname{deg}_{S}(v)}{2}. h ( F ) := S ∈ E ( F ) max v ∈ V ( F ) max 2 deg S ( v ) . So h ( F ) = 0 h(F)=0 h ( F ) = 0 if and only if F F F is a forest.
By Theorem A.11 , τ ( F ; ⋅ ) \tau(F;\cdot) τ ( F ; ⋅ ) is a polynomial with nonnegative integer coefficients in m 1 , … , m h ( F ) m_{1},\ldots,m_{h(F)} m 1 , … , m h ( F ) , and it genuinely involves m h ( F ) m_{h(F)} m h ( F ) (the maximizing S S S contributes a monomial containing it).
Moment matching and motif matching
Theorem A.14 (Motif transfer). Let Θ 1 , Θ 2 \Theta_{1},\Theta_{2} Θ 1 , Θ 2 share the radial law R R R , and let j ≥ 0 j \ge0 j ≥ 0 .
If Θ 1 ∼ j Θ 2 \Theta_{1} \sim_{j} \Theta_{2} Θ 1 ∼ j Θ 2 , then t ( F ; Θ 1 ) = t ( F ; Θ 2 ) t(F;\Theta_{1})=t(F;\Theta_{2}) t ( F ; Θ 1 ) = t ( F ; Θ 2 ) for every F F F with h ( F ) ≤ j h(F)\le j h ( F ) ≤ j .
If Θ 1 ∼ j o Θ 2 \Theta_{1} \sim_{j}^{o} \Theta_{2} Θ 1 ∼ j o Θ 2 and m j ( Θ 1 ) > m j ( Θ 2 ) m_{j}(\Theta_{1})>m_{j}(\Theta_{2}) m j ( Θ 1 ) > m j ( Θ 2 ) , then t ( F ; Θ 1 ) > t ( F ; Θ 2 ) t(F;\Theta_{1})>t(F;\Theta_{2}) t ( F ; Θ 1 ) > t ( F ; Θ 2 ) for every F F F with h ( F ) = j h(F)=j h ( F ) = j .
Proof. (1) By Theorem A.11 , τ ( F ; ⋅ ) \tau(F;\cdot) τ ( F ; ⋅ ) depends only on m 0 , … , m h ( F ) m_{0},\ldots,m_{h(F)} m 0 , … , m h ( F ) , all of which agree. Apply Lemma A.9 .
(2) Each term of Theorem A.11 has the form m j p S ⋅ c S m_{j}^{p_{S}}\cdot c_{S} m j p S ⋅ c S , where p S ≥ 0 p_{S}\ge0 p S ≥ 0 counts vertices with deg S ( v ) = 2 j \operatorname{deg}_{S}(v)=2j deg S ( v ) = 2 j and c S > 0 c_{S}>0 c S > 0 is a product of the matched moments m 0 , … , m j − 1 m_{0},\ldots,m_{j-1} m 0 , … , m j − 1 (all positive by Proposition A.1 ). Terms with p S = 0 p_{S}=0 p S = 0 agree. Terms with p S ≥ 1 p_{S}\ge1 p S ≥ 1 satisfy m j ( Θ 1 ) p S c S > m j ( Θ 2 ) p S c S m_{j}(\Theta_{1})^{p_{S}}c_{S}>m_{j}(\Theta_{2})^{p_{S}}c_{S} m j ( Θ 1 ) p S c S > m j ( Θ 2 ) p S c S because m j > 0 m_{j}>0 m j > 0 under both. At least one such term exists because h ( F ) = j h(F)=j h ( F ) = j . The radial prefactor is common and positive.
Remark. Part (2) is why near perfect matching ∼ j o \sim_{j}^{o} ∼ j o is the natural relation: the separation needs only the order of the first unmatched moment, not its value, and there is no cancellation. For h ( F ) > j h(F)>j h ( F ) > j , t ( F ) t(F) t ( F ) also involves m j + 1 , m j + 2 , … m_{j+1},m_{j+2},\ldots m j + 1 , m j + 2 , … , which are unconstrained by ∼ j o \sim_{j}^{o} ∼ j o ; whether such F F F separate every pair is not implied by this theorem.
Combinatorics of the slope index
Proposition A.15. Let Δ ( F ) \Delta(F) Δ ( F ) be the maximum degree of F F F .
h ( F ) ≤ ⌊ Δ ( F ) / 2 ⌋ h(F) \le\lfloor\Delta(F)/2 \rfloor h ( F ) ≤ ⌊ Δ ( F ) /2 ⌋ .
If h ( F ) ≥ j ≥ 1 h(F) \ge j \ge1 h ( F ) ≥ j ≥ 1 then ∣ V ( F ) ∣ ≥ 2 j + 1 |V(F)| \ge2j+1 ∣ V ( F ) ∣ ≥ 2 j + 1 .
Proof. (1) deg S ( v ) ≤ deg F ( v ) \deg_S(v) \le\deg_F(v) deg S ( v ) ≤ deg F ( v ) and deg S ( v ) \deg_S(v) deg S ( v ) is even. (2) A vertex with deg S ( v ) ≥ 2 j \deg_S(v) \ge2j deg S ( v ) ≥ 2 j has at least 2 j 2j 2 j distinct neighbours. □ \square □
Part (1) is stronger than a vertex count: under ∼ j \sim_j ∼ j every graph of maximum degree at most 2 j + 1 2j+1 2 j + 1 is matched, however many vertices it has.
Example A.16 (Friendship graph). Let F r Fr F r (r ≥ 1 r \ge1 r ≥ 1 ) be r r r triangles sharing one common vertex (the center ), so ∣ V ( F r ) ∣ = 2 r + 1 |V(Fr)| = 2r+1 ∣ V ( F r ) ∣ = 2 r + 1 and Δ ( F r ) = 2 r \Delta(Fr) = 2r Δ ( F r ) = 2 r . The blocks of F r Fr F r are its triangles, and the cycle space is the direct sum of the cycle spaces of the blocks, so the even subsets are exactly the unions of i i i of the r r r triangles, 0 ≤ i ≤ r 0 \le i \le r 0 ≤ i ≤ r . Such a union gives the center degree 2 i 2i 2 i and gives 2 i 2i 2 i outer vertices degree 2. Hence
t ( F r ; Θ ) = ρ 2 r ρ 2 2 r ∑ i = 0 r ( r i ) m 1 2 i m i , h ( F r ) = r . t(Fr;\Theta) = \rho_{2r}\rho_2^{2r}\sum_{i=0}^{r}\binom{r}{i}m_1^{2i}m_i,\qquad h(Fr)=r. t ( F r ; Θ ) = ρ 2 r ρ 2 2 r i = 0 ∑ r ( i r ) m 1 2 i m i , h ( F r ) = r . The top moment m r m_r m r enters with coefficient ρ 2 r ρ 2 2 r m 1 2 r \rho_{2r}\rho_2^{2r}m_1^{2r} ρ 2 r ρ 2 2 r m 1 2 r .
Proposition A.17 (Graphs of minimal order with h ( F ) = j h(F)=j h ( F ) = j ). Let j ≥ 1 j \ge1 j ≥ 1 and ∣ V ( F ) ∣ = 2 j + 1 |V(F)| = 2j+1 ∣ V ( F ) ∣ = 2 j + 1 . Then h ( F ) = j h(F)=j h ( F ) = j if and only if F F F has a vertex v v v adjacent to all other vertices such that every connected component of F [ N ( v ) ] F[N(v)] F [ N ( v )] (the subgraph induced on the neighbours of v v v ) has an even number of vertices. F j F_j F j is the edge-minimal such graph.
Proof. (⇒ \Rightarrow ⇒ ) Take S ∈ E ( F ) S \in\mathcal{E}(F) S ∈ E ( F ) and v v v with deg S ( v ) = 2 j = ∣ V ( F ) ∣ − 1 \deg_S(v)=2j=|V(F)|-1 deg S ( v ) = 2 j = ∣ V ( F ) ∣ − 1 . Then v v v is adjacent (through S S S ) to every other vertex. Let S ′ = S ∩ E ( F [ N ( v ) ] ) S'=S \cap E(F[N(v)]) S ′ = S ∩ E ( F [ N ( v )]) . For each u ≠ v u \ne v u = v , deg S ( u ) = 1 + deg S ′ ( u ) \deg_S(u)=1+\deg_{S'}(u) deg S ( u ) = 1 + deg S ′ ( u ) is even, so every vertex of F [ N ( v ) ] F[N(v)] F [ N ( v )] has odd degree in S ′ S' S ′ . By the handshake lemma applied to each component, every component of F [ N ( v ) ] F[N(v)] F [ N ( v )] has even order.
(⇐ \Leftarrow ⇐ ) In each component of F [ N ( v ) ] F[N(v)] F [ N ( v )] , pair up its vertices arbitrarily and choose a path inside the component between each pair. Let S ′ S' S ′ be the symmetric difference of the edge sets of all these paths. The parity of deg S ′ ( u ) \deg_{S'}(u) deg S ′ ( u ) equals the number of paths having u u u as an endpoint, which is one, so every vertex of N ( v ) N(v) N ( v ) has odd degree in S ′ S' S ′ . Then S = S ′ ∪ { v u : u ∈ N ( v ) } S=S'\cup\{vu:u\in N(v)\} S = S ′ ∪ { v u : u ∈ N ( v )} is even with deg S ( v ) = 2 j \deg_S(v)=2j deg S ( v ) = 2 j , so h ( F ) ≥ j h(F)\ge j h ( F ) ≥ j , and h ( F ) ≤ j h(F)\le j h ( F ) ≤ j by Proposition A.15.
Edge-minimality: v v v needs 2 j 2j 2 j edges, and F [ N ( v ) ] F[N(v)] F [ N ( v )] needs at least j j j edges (a graph on 2 j 2j 2 j vertices with no isolated vertices has at least j j j edges). F j F_j F j attains 3 j 3j 3 j . □ \square □
Corollary A.18 (Census transfer). Let Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 share R R R , and let j ≥ 0 j \ge0 j ≥ 0 .
If Θ 1 ∼ j Θ 2 \Theta_1 \sim_j \Theta_2 Θ 1 ∼ j Θ 2 then Cen 2 j + 2 ( Θ 1 ) = Cen 2 j + 2 ( Θ 2 ) \operatorname{Cen}_{2j+2}(\Theta_1)=\operatorname{Cen}_{2j+2}(\Theta_2) Cen 2 j + 2 ( Θ 1 ) = Cen 2 j + 2 ( Θ 2 ) .
If Θ 1 ∼ j + 1 ∘ Θ 2 \Theta_1 \sim^{\circ}_{j+1} \Theta_2 Θ 1 ∼ j + 1 ∘ Θ 2 and m j + 1 ( Θ 1 ) ≠ m j + 1 ( Θ 2 ) m_{j+1}(\Theta_1)\ne m_{j+1}(\Theta_2) m j + 1 ( Θ 1 ) = m j + 1 ( Θ 2 ) then Cen 2 j + 3 ( Θ 1 ) ≠ Cen 2 j + 3 ( Θ 2 ) \operatorname{Cen}_{2j+3}(\Theta_1)\ne\operatorname{Cen}_{2j+3}(\Theta_2) Cen 2 j + 3 ( Θ 1 ) = Cen 2 j + 3 ( Θ 2 ) . Among graphs on exactly 2 j + 3 2j+3 2 j + 3 vertices, the densities that differ are exactly those of the graphs characterized in Proposition A.17 (with j + 1 j+1 j + 1 in place of j j j ), and each differs with the sign of m j + 1 ( Θ 1 ) − m j + 1 ( Θ 2 ) m_{j+1}(\Theta_1)-m_{j+1}(\Theta_2) m j + 1 ( Θ 1 ) − m j + 1 ( Θ 2 ) . For j ≥ 1 j\ge1 j ≥ 1 the friendship graph gives
t ( F j + 1 ; Θ 1 ) − t ( F j + 1 ; Θ 2 ) = ρ 2 j + 2 ρ 2 2 j + 2 m 1 2 j + 2 ( m j + 1 ( Θ 1 ) − m j + 1 ( Θ 2 ) ) . t(F_{j+1};\Theta_1)-t(F_{j+1};\Theta_2)=\rho_{2j+2}\rho_2^{2j+2}m_1^{2j+2}\bigl(m_{j+1}(\Theta_1)-m_{j+1}(\Theta_2)\bigr). t ( F j + 1 ; Θ 1 ) − t ( F j + 1 ; Θ 2 ) = ρ 2 j + 2 ρ 2 2 j + 2 m 1 2 j + 2 ( m j + 1 ( Θ 1 ) − m j + 1 ( Θ 2 ) ) .
Proof. (1) If ∣ V ( F ) ∣ ≤ 2 j + 2 |V(F)| \le2j+2 ∣ V ( F ) ∣ ≤ 2 j + 2 then h ( F ) ≤ j h(F) \le j h ( F ) ≤ j by Proposition A.15 (2); apply Theorem A.14 (1).
(2) A graph on 2 j + 3 2j+3 2 j + 3 vertices has h ( F ) ≤ j + 1 h(F) \le j+1 h ( F ) ≤ j + 1 . If h ( F ) ≤ j h(F) \le j h ( F ) ≤ j its density agrees (Theorem A.14 (1), since ∼ j + 1 o \sim_{j+1}^{o} ∼ j + 1 o implies ∼ j \sim_j ∼ j ). If h ( F ) = j + 1 h(F)=j+1 h ( F ) = j + 1 it differs, with the stated sign (Theorem A.14 (2)). Proposition A.17 identifies the graphs with h ( F ) = j + 1 h(F)=j+1 h ( F ) = j + 1 . For the displayed formula, use Example A.16 : every term with i ≤ j i \le j i ≤ j cancels, and m 1 m_1 m 1 is matched when j ≥ 1 j \ge1 j ≥ 1 .
Remark. Section A.4 applies Corollary A.18 with j = K − 2 j=K-2 j = K − 2 to the fibers constructed in Sections A.2 and A.3.
Configuration Construction for K K K even
Given a configuration Θ \Theta Θ , it is straightforward to compute the moments m j m_j m j and the matrix M \mathbf{M} M . However, in this subsection we show the reverse. Given the moments m j m_j m j up until a particular j j j , we show how to construct a configuration that realizes those moments (provided they are realizable). Furthermore, we show how to construct such a configuration from a “seed” real number ξ \xi ξ which can vary. Therefore, we show how to construct a family of configurations that all realize those moments.
In outline: given a ξ ∈ R \xi\in\mathbb{R} ξ ∈ R , we would like to construct the matrix J ( ξ ) J(\xi) J ( ξ ) . The eigenvalues of J ( ξ ) J(\xi) J ( ξ ) will show us how to construct the slopes s i s_i s i and the eigenvectors of J ( ξ ) J(\xi) J ( ξ ) will show us how to construct the weights w i w_i w i . Care must be taken so that the eigenvalues exist and are positive, that the community weights are positive and sum up to 1 1 1 , and that the resulting dot products always land in [ 0 , 1 ] [0,1] [ 0 , 1 ] . These conditions will limit the range of ξ \xi ξ we can choose, and will be addressed in the admissibility analysis later on. For now, assume that we are given a range [ ξ − , ξ + ] [\xi^-,\xi^+] [ ξ − , ξ + ] such that the resulting matrix always has positive eigenvalues, and the resulting configuration will be admissible.
We divide our analysis into even and odd K K K . In this section we first consider the case of K K K even.
Definition A.19 (Construction of Θ \Theta Θ for K K K even). Let K = 2 k K=2k K = 2 k . Suppose ξ ∈ [ ξ − , ξ + ] ⊂ R \xi\in[\xi^-,\xi^+] \subset\mathbb{R} ξ ∈ [ ξ − , ξ + ] ⊂ R , and let m 0 = 1 , m 1 , … , m 2 k − 2 m_0=1,m_1,\ldots,m_{2k-2} m 0 = 1 , m 1 , … , m 2 k − 2 be the desired moments. Call ν ~ \tilde{\nu} ν ~ the probability measure that generated these moments (corresponding to the “reference configuration”).
Let M k \mathbf{M}_k M k be the moment matrix constructed as per Definition A.2 (call this the Hankel matrix), and let M k = U T U \mathbf{M}_k=U^{T}U M k = U T U be its Cholesky decomposition (so U U U is k × k k \times k k × k ). Note that U U U is therefore upper triangular and positive diagonal. Set:
a 0 = U 1 , 2 U 1 , 1 a_0 = \frac{U_{1,2}}{U_{1,1}} a 0 = U 1 , 1 U 1 , 2 a j = U j + 1 , j + 2 U j + 1 , j + 1 − U j , j + 1 U j , j , 1 ≤ j ≤ k − 2 a_j = \frac{U_{j+1,j+2}}{U_{j+1,j+1}}-\frac{U_{j,j+1}}{U_{j,j}}, \qquad1 \le j \le k-2 a j = U j + 1 , j + 1 U j + 1 , j + 2 − U j , j U j , j + 1 , 1 ≤ j ≤ k − 2 b j = U j + 1 , j + 1 U j , j , 1 ≤ j ≤ k − 1 b_j = \frac{U_{j+1,j+1}}{U_{j,j}}, \qquad1 \le j \le k-1 b j = U j , j U j + 1 , j + 1 , 1 ≤ j ≤ k − 1 J ( ξ ) = ( a 0 b 1 b 1 a 1 ⋱ ⋱ ⋱ b k − 1 b k − 1 ξ ) J(\xi)=
\begin{pmatrix}
a_0 & b_1 & & & \\
b_1 & a_1 & \ddots& & \\
& \ddots& \ddots& b_{k-1} & \\
& & b_{k-1} & \xi
\end{pmatrix} J ( ξ ) = a 0 b 1 b 1 a 1 ⋱ ⋱ ⋱ b k − 1 b k − 1 ξ Let t 1 > ⋯ > t k t_1>\cdots>t_k t 1 > ⋯ > t k be the eigenvalues of J ( ξ ) J(\xi) J ( ξ ) . Assume ξ − , ξ + \xi^-,\xi^+ ξ − , ξ + are such that the resulting eigenvalues are all positive. Set s i = t i s_i=\sqrt{t_i} s i = t i for i ≤ k i \le k i ≤ k and s i = − s K + 1 − i s_i=-s_{K+1-i} s i = − s K + 1 − i for i > k i>k i > k to be the slopes of the configuration.
Let v i v_i v i be the corresponding orthonormal eigenvectors. Let w i = 1 2 ( v i ) 1 2 w_i = \frac{1}{2}(v_i)_1^2 w i = 2 1 ( v i ) 1 2 (half the squared first component of v i v_i v i ) be the weights of the configuration for i ≤ k i \le k i ≤ k , and w i = w K + 1 − i w_i = w_{K+1-i} w i = w K + 1 − i for i > k i > k i > k . When k = 1 k = 1 k = 1 there are no coefficients a j a_j a j , b j b_j b j and J ( ξ ) = [ ξ ] J(\xi) = [\xi] J ( ξ ) = [ ξ ] .
Call ν ξ \nu_\xi ν ξ the probability measure corresponding to this configuration.
The eigenvalues and eigenvectors of J ( ξ ) J(\xi) J ( ξ ) can be found using numerical methods, but later in § 4 we will provide an explicit example for K = 4 K = 4 K = 4 (or k = 2 k = 2 k = 2 ). Now we shall prove that this construction achieves the desired moments.
Moment Matching Correctness
First in the space of all polynomials with degree ≤ k − 1 \le k - 1 ≤ k − 1 , let us define the inner product ⟨ p , q ⟩ = E [ p ( s 2 ) q ( s 2 ) ] \langle p,q\rangle= \mathbb{E}[p(s^2)q(s^2)] ⟨ p , q ⟩ = E [ p ( s 2 ) q ( s 2 )] . This inner product is well defined on that space, i.e. positive definite: the reference law of s 2 s^2 s 2 has exactly k k k atoms, and a nonzero polynomial of degree at most k − 1 k-1 k − 1 cannot vanish at all of them. In particular M k M_k M k is positive definite, so the Cholesky decomposition used in Definition A.19 exists.
Note that because the space is limited to polynomials of degree ≤ k − 1 \le k - 1 ≤ k − 1 , the expectations go up to the m 2 k − 2 m_{2k-2} m 2 k − 2 which is given. In other words, these inner products exist, and can be assumed to be taken under the probability measure induced by the given moments.
Definition A.20 (Polynomial Basis). Let ⟨ p , q ⟩ = E [ p ( s 2 ) q ( s 2 ) ] \langle p,q\rangle= \mathbb{E}[p(s^2)q(s^2)] ⟨ p , q ⟩ = E [ p ( s 2 ) q ( s 2 )] , and let f 0 , … , f k − 1 f_0,\ldots,f_{k-1} f 0 , … , f k − 1 be an orthogonal basis such that f j f_j f j is monic and has degree exactly j j j . We can get such a basis by running Gram-Schmidt on 1 , x , x 2 , … , x k − 1 1,x,x^2,\ldots,x^{k-1} 1 , x , x 2 , … , x k − 1 for example.
This definition also means that ⟨ x i , x j ⟩ = m i + j \langle x^i,x^j\rangle= m_{i+j} ⟨ x i , x j ⟩ = m i + j . Also, orthogonality requires that ⟨ f i , f j ⟩ = 0 \langle f_i,f_j\rangle= 0 ⟨ f i , f j ⟩ = 0 for i ≠ j i \ne j i = j . In other words, f j f_j f j is orthogonal to any polynomial with degree less than j j j .
Proposition A.21. The basis f j ( x ) f_j(x) f j ( x ) as defined above must satisfy the following initial conditions and recurrence relation:
f 0 ( x ) = 1 f 1 ( x ) = x − m 1 f j + 1 ( x ) = ( x − a ~ j ) f j ( x ) − b ~ j 2 f j − 1 ( x ) \begin{aligned}
f_0(x) &= 1 \\
f_1(x) &= x-m_1 \\
f_{j+1}(x) &= (x-\widetilde{a}_j)f_j(x)-\widetilde{b}_j^2f_{j-1}(x)
\end{aligned} f 0 ( x ) f 1 ( x ) f j + 1 ( x ) = 1 = x − m 1 = ( x − a j ) f j ( x ) − b j 2 f j − 1 ( x ) for j = 1 , … , k − 2 j=1,\ldots,k-2 j = 1 , … , k − 2 where
a ~ j = ⟨ x f j , f j ⟩ ∣ f j ∣ 2 \widetilde{a}_j = \frac{\langle xf_j,f_j\rangle}{\lvert f_j\rvert^2} a j = ∣ f j ∣ 2 ⟨ x f j , f j ⟩ b ~ j 2 = ∣ f j ∣ 2 ∣ f j − 1 ∣ 2 \widetilde{b}_j^2 = \frac{\lvert f_j\rvert^2}{\lvert f_{j-1}\rvert^2} b j 2 = ∣ f j − 1 ∣ 2 ∣ f j ∣ 2
Proof. f 0 ( x ) = 1 f_0(x)=1 f 0 ( x ) = 1 is obvious. Since f 1 f_1 f 1 has to be a linear function, f 1 ( x ) = x − c f_1(x)=x-c f 1 ( x ) = x − c for some c c c . But ⟨ f 1 , f 0 ⟩ = m 1 − c = 0 \langle f_1,f_0\rangle=m_1-c=0 ⟨ f 1 , f 0 ⟩ = m 1 − c = 0 so c = m 1 c=m_1 c = m 1 .
Next, note that multiplication by x x x is self-adjoint: ⟨ x p , q ⟩ = E [ s 2 p ( s 2 ) q ( s 2 ) ] = ⟨ p , x q ⟩ \langle xp,q\rangle=\mathbb{E}[s^2p(s^2)q(s^2)]=\langle p,xq\rangle ⟨ x p , q ⟩ = E [ s 2 p ( s 2 ) q ( s 2 )] = ⟨ p , x q ⟩ .
Now, f 0 , … , f j f_0,\ldots,f_j f 0 , … , f j are the orthogonal basis for polynomials of degree ≤ j \le j ≤ j . Consider the polynomial f j + 1 − x f j f_{j+1}-xf_j f j + 1 − x f j . Both terms are monic polynomials of degree j + 1 j+1 j + 1 , so their difference has degree at most j j j . Therefore there exist c 0 , … , c j c_0,\ldots,c_j c 0 , … , c j such that:
f j + 1 − x f j = c 0 f 0 + ⋯ + c j f j f_{j+1}-xf_j=c_0f_0+\cdots+c_jf_j f j + 1 − x f j = c 0 f 0 + ⋯ + c j f j
When we apply inner product ⟨ ⋅ , f i ⟩ \langle\cdot,f_i\rangle ⟨ ⋅ , f i ⟩ for i = 0 , … , j i=0,\ldots,j i = 0 , … , j . Note that f i f_i f i is orthogonal to any polynomial with degree less than i i i , so there are very few survivors. In the LHS:
⟨ f j + 1 − x f j , f i ⟩ = − ⟨ x f j , f i ⟩ = − ⟨ f j , x f i ⟩ \langle f_{j+1}-xf_j,f_i\rangle=-\langle xf_j,f_i\rangle=-\langle f_j,xf_i\rangle ⟨ f j + 1 − x f j , f i ⟩ = − ⟨ x f j , f i ⟩ = − ⟨ f j , x f i ⟩
so the only survivors are i = j − 1 i=j-1 i = j − 1 (because x f i xf_i x f i has degree j j j ) and i = j i=j i = j (because x f j xf_j x f j has degree j + 1 j+1 j + 1 ). On the RHS, for a particular i i i , the only survivor is c i ∣ f i ∣ 2 c_i|f_i|^2 c i ∣ f i ∣ 2 . Therefore:
c j − 1 = − ⟨ f j , x f j − 1 ⟩ ∣ f j − 1 ∣ 2 , c j = − ⟨ x f j , f j ⟩ ∣ f j ∣ 2 c_{j-1}=-\frac{\langle f_j,xf_{j-1}\rangle}{|f_{j-1}|^2},\qquad c_j=-\frac{\langle xf_j,f_j\rangle}{|f_j|^2} c j − 1 = − ∣ f j − 1 ∣ 2 ⟨ f j , x f j − 1 ⟩ , c j = − ∣ f j ∣ 2 ⟨ x f j , f j ⟩
We can see c j = − a ~ j c_j=-\widetilde{a}_j c j = − a j readily. But for c j − 1 c_{j-1} c j − 1 , notice that x f j − 1 xf_{j-1} x f j − 1 is again a monic polynomial of degree j j j , which can be expressed as f j f_j f j plus a polynomial of degree less than j j j . Therefore ⟨ f j , x f j − 1 ⟩ = ∣ f j ∣ 2 \langle f_j,xf_{j-1}\rangle=|f_j|^2 ⟨ f j , x f j − 1 ⟩ = ∣ f j ∣ 2 , and c j − 1 = − b ~ j 2 c_{j-1}=-\widetilde{b}_j^2 c j − 1 = − b j 2 . The recurrence then holds.
Remark. Proposition A.21 is a statement about uniqueness. We started with the assumption about inner product and orthogonality, and derived the recurrence. This is why the proposition asserts “must satisfy”. Later we shall make use of this uniqueness result.
Remark. Note that f 1 f_1 f 1 also satisfies the recurrence formula if we let b ~ 0 f − 1 \widetilde{b}_0f_{-1} b 0 f − 1 terms as absent. There is nothing “special” about the case j = 0 j=0 j = 0 .
Remark. The recurrence stops when j = k − 2 j=k-2 j = k − 2 at which point we get f k − 1 f_{k-1} f k − 1 which is what we need as a basis for the space. That means a ~ k − 2 \widetilde{a}_{k-2} a k − 2 is the highest order a ~ \widetilde{a} a defined. But there is nothing stopping us from calculating a ~ k − 1 \widetilde{a}_{k-1} a k − 1 since f k − 1 f_{k-1} f k − 1 is well defined. In fact, all the previous a ~ \widetilde{a} a requires computing m 2 k − 2 m_{2k-2} m 2 k − 2 , which are given (to be matched). So this is the first non-zero moment that lives outside the matched data, and this is the reason behind our main theorem as we shall later see.
Remark. There is a nice interpretation for a ~ j = E [ x f j ( x ) 2 ] E [ f j ( x ) 2 ] \widetilde{a}_j=\frac{\mathbb{E}[xf_j(x)^2]}{\mathbb{E}[f_j(x)^2]} a j = E [ f j ( x ) 2 ] E [ x f j ( x ) 2 ] , the mean of x x x under the reweighted measure of f j ( x ) 2 f_j(x)^2 f j ( x ) 2 . The weights are non-negative, so s k 2 ≤ a ~ j ≤ s 1 2 s_k^2\leq\widetilde{a}_j\leq s_1^2 s k 2 ≤ a j ≤ s 1 2 for all j j j . Later we shall see that this interpretation allows us to derive the range of ξ \xi ξ that is admissible.
Now we shall prove that a ~ , b ~ \widetilde{a},\widetilde{b} a , b as defined in Proposition A.21 is the same as the one in Definition A.19.
Proposition A.22. Given the definitions of a ~ j , a j , b ~ j , b j \widetilde{a}_j,a_j,\widetilde{b}_j,b_j a j , a j , b j , b j and the fact that M k = U T U \mathbf{M}_k=U^TU M k = U T U , we have:
a j = a ~ j 1 ≤ j ≤ k − 2 a_j=\widetilde{a}_j\qquad1\leq j\leq k-2 a j = a j 1 ≤ j ≤ k − 2 b j = b ~ j 1 ≤ j ≤ k − 1 b_j=\widetilde{b}_j\qquad1\leq j\leq k-1 b j = b j 1 ≤ j ≤ k − 1
Proof. M a , b = m a + b − 2 = E [ s 2 ( a + b − 2 ) ] = E [ s 2 a − 2 s 2 b − 2 ] = ⟨ x a − 1 , x b − 1 ⟩ \mathbf{M}_{a,b}=m_{a+b-2}=\mathbb{E}[s^{2(a+b-2)}]=\mathbb{E}[s^{2a-2}s^{2b-2}]=\langle x^{a-1},x^{b-1}\rangle M a , b = m a + b − 2 = E [ s 2 ( a + b − 2 ) ] = E [ s 2 a − 2 s 2 b − 2 ] = ⟨ x a − 1 , x b − 1 ⟩ . So M \mathbf{M} M is the Gram matrix of the monomial basis 1 , x , … , x k − 1 1,x,\ldots,x^{k-1} 1 , x , … , x k − 1 , which is not necessarily orthogonal. However, Cholesky decomposition is a unique decomposition that decomposes any basis into orthonormal basis components.
Define p i p_i p i to be the scaled version of f i f_i f i such that its magnitude is one.
p i : = f i ∣ f i ∣ p_i:=\frac{f_i}{|f_i|} p i := ∣ f i ∣ f i
Define G G G to be a k × k k\times k k × k matrix such that G i j : = ⟨ x j − 1 , p i − 1 ⟩ G_{ij}:=\langle x^{j-1},p_{i-1}\rangle G ij := ⟨ x j − 1 , p i − 1 ⟩ . Note that because f i f_i f i is orthogonal to any polynomial with degree less than i i i , then G G G is upper triangular. The diagonal G j , j = ⟨ x j − 1 , p j − 1 ⟩ = ∣ f j − 1 ∣ > 0 G_{j,j}=\langle x^{j-1},p_{j-1}\rangle=|f_{j-1}|>0 G j , j = ⟨ x j − 1 , p j − 1 ⟩ = ∣ f j − 1 ∣ > 0 . Next, we note that x a − 1 = ∑ i G i , a p i − 1 x^{a-1}=\sum_i G_{i,a}p_{i-1} x a − 1 = ∑ i G i , a p i − 1 by the definition of G G G . So M a , b = ⟨ x a − 1 , x b − 1 ⟩ = ∑ i G i , a G i , b = ( G T G ) a , b \mathsf{M}_{a,b}=\langle x^{a-1},x^{b-1}\rangle=\sum_i G_{i,a}G_{i,b}=(G^{T}G)_{a,b} M a , b = ⟨ x a − 1 , x b − 1 ⟩ = ∑ i G i , a G i , b = ( G T G ) a , b , so then we must have G = U G=U G = U . Then:
b ~ j = ∣ f j ∣ ∣ f j − 1 ∣ = U j + 1 , j + 1 U j , j = b j \widetilde{b}_j=\frac{|f_j|}{|f_{j-1}|}=\frac{U_{j+1,j+1}}{U_{j,j}}=b_j b j = ∣ f j − 1 ∣ ∣ f j ∣ = U j , j U j + 1 , j + 1 = b j
Now, since f j f_j f j is a monic polynomial of degree j j j , we can write:
f j = x j + γ j x j − 1 + … f_j=x^j+\gamma_jx^{j-1}+\ldots f j = x j + γ j x j − 1 + …
(i.e. γ j \gamma_j γ j is the subleading coefficient in f j f_j f j ). Matching the coefficients in the recurrence in Proposition A.21 versus the above, we have: a ~ j = γ j − γ j + 1 \widetilde{a}_j=\gamma_j-\gamma_{j+1} a j = γ j − γ j + 1 .
Now let us express x j x^j x j in terms of the basis p 0 , … , p j p_0,\ldots,p_j p 0 , … , p j :
x j = ∑ i = 0 j ⟨ x j , p i ⟩ p i = ∑ i = 0 j U i + 1 , j + 1 f i ∣ f i ∣ = ∑ i = 0 j U i + 1 , j + 1 f i U i + 1 , i + 1 x^j=\sum_{i=0}^{j}\langle x^j,p_i\rangle p_i=\sum_{i=0}^{j}U_{i+1,j+1}\frac{f_i}{|f_i|}=\sum_{i=0}^{j}\frac{U_{i+1,j+1}f_i}{U_{i+1,i+1}} x j = i = 0 ∑ j ⟨ x j , p i ⟩ p i = i = 0 ∑ j U i + 1 , j + 1 ∣ f i ∣ f i = i = 0 ∑ j U i + 1 , i + 1 U i + 1 , j + 1 f i
Now compare the coefficients of x j − 1 x^{j-1} x j − 1 . In the LHS it is zero. In the RHS, f j f_j f j term contributes U j + 1 , j + 1 U j + 1 , j + 1 γ j = γ j \frac{U_{j+1,j+1}}{U_{j+1,j+1}}\gamma_j=\gamma_j U j + 1 , j + 1 U j + 1 , j + 1 γ j = γ j . And f j − 1 f_{j-1} f j − 1 term contributes U j , j + 1 U j , j \frac{U_{j,j+1}}{U_{j,j}} U j , j U j , j + 1 . So:
γ j = − U j , j + 1 U j , j 1 ≤ j ≤ k − 1 \gamma_j=-\frac{U_{j,j+1}}{U_{j,j}}\quad1\leq j\leq k-1 γ j = − U j , j U j , j + 1 1 ≤ j ≤ k − 1
From this we get a j = a ~ j a_j=\widetilde{a}_j a j = a j for 1 ≤ j ≤ k − 2 1\leq j\leq k-2 1 ≤ j ≤ k − 2 . The only thing we need to prove now is the base case a 0 a_0 a 0 . But that is evident because f 1 = x − m 1 f_1=x-m_1 f 1 = x − m 1 so γ 1 = − m 1 \gamma_1=-m_1 γ 1 = − m 1
Now we have shown that most entries in the matrix J ( ξ ) J(\xi) J ( ξ ) are indeed recurrence coefficients for an orthogonal monic basis for the moments of s 2 s^2 s 2 , and gave an interpretation of those coefficients. Now we connect them to the parameters of the configuration Θ \Theta Θ .
Proposition A.23 (Structural Admissibility). The configuration Θ \Theta Θ constructed in Definition A.19 gives community weights that are positive and sum up to one, and that all eigenvalues (and consequently line slopes) are all distinct.
Proof. Let V V V be the matrix of eigenvectors and Λ \Lambda Λ be a diagonal matrix of eigenvalues, so that J = V Λ V − 1 J=V\Lambda V^{-1} J = V Λ V − 1 . Then let J d = V Λ d V − 1 J^d=V\Lambda^dV^{-1} J d = V Λ d V − 1 for any d d d . Also recall that because J J J is symmetric, then V T = V − 1 V^T=V^{-1} V T = V − 1 so J d = V Λ d V T J^d=V\Lambda^dV^T J d = V Λ d V T . Then, under the probability measure ν ξ \nu_\xi ν ξ :
E ν ξ [ s 2 d ] = ∑ i = 1 2 k w i ξ i 2 d = 2 ∑ i = 1 k w i ξ i 2 d = ∑ i = 1 k ( v i ) 1 2 t i 2 d = ( J d ) 1 , 1 \mathbb{E}_{\nu_\xi}\left[s^{2d}\right]=\sum_{i=1}^{2k}w_i\xi_i^{2d}=2\sum_{i=1}^{k}w_i\xi_i^{2d}=\sum_{i=1}^{k}(v_i)_1^2t_i^{2d}=(J^d)_{1,1} E ν ξ [ s 2 d ] = i = 1 ∑ 2 k w i ξ i 2 d = 2 i = 1 ∑ k w i ξ i 2 d = i = 1 ∑ k ( v i ) 1 2 t i 2 d = ( J d ) 1 , 1
For example when we set d = 0 d=0 d = 0 we get m 0 = 1 = ∑ w i m_0=1=\sum w_i m 0 = 1 = ∑ w i so we are guaranteed to get total community weights of 1.
Also because all b j > 0 b_j>0 b j > 0 then J J J is unreduced. No eigenvector has first entry zero. Indeed, write ( v ) i (v)_i ( v ) i for the components of an eigenvector v v v . If ( v ) 1 = 0 (v)_1=0 ( v ) 1 = 0 , then row 1 of ( J − λ I ) v = 0 (J-\lambda I)v=0 ( J − λ I ) v = 0 gives b 1 ( v ) 2 = 0 b_1(v)_2=0 b 1 ( v ) 2 = 0 , so ( v ) 2 = 0 (v)_2=0 ( v ) 2 = 0 . Then row 2 gives b 2 ( v ) 3 = 0 b_2(v)_3=0 b 2 ( v ) 3 = 0 , and so on, so all components of v v v are zero, i.e. v = 0 v=0 v = 0 , which is not an eigenvector. Also, the same process of reading the rows of ( J − λ I ) v (J-\lambda I)v ( J − λ I ) v completely determines v v v , so the eigenvalues are all distinct and the eigenvectors all have nonzero first entry. Therefore this construction gives communities that are distinct, all have positive weights, and the weights sum up to 1. This is why we call this Structural Admissibility. Note that we have yet to prove that the eigenvalues are all positive.
Let e j e_j e j be the coordinate vectors of the j j j -th basis (zero everywhere but 1 at j j j -th element). We have seen in the proof above the significance of J d J^d J d . Now we can apply f f f to J J J .
Lemma A.24. For all 0 ≤ j ≤ k − 1 0 \le j \le k - 1 0 ≤ j ≤ k − 1 , if f j f_j f j and J J J are as defined in Definitions A.19 and A.20, then:
f j ( J ) e 1 = ∣ f j ∣ e j + 1 f_j(J)e_1 = \lvert f_j\rvert e_{j+1} f j ( J ) e 1 = ∣ f j ∣ e j + 1
Proof. For j = 0 j = 0 j = 0 , it is immediate. For j = 1 j = 1 j = 1 , f 1 ( J ) e 1 = ( J − m 1 I ) e 1 f_1(J)e_1 = (J - m_1I)e_1 f 1 ( J ) e 1 = ( J − m 1 I ) e 1 . The first element is a 0 − m 1 = 0 a_0 - m_1 = 0 a 0 − m 1 = 0 , the second element is b 1 b_1 b 1 , so this is b 1 e 2 b_1e_2 b 1 e 2 . But ∣ f 1 ∣ = ∣ f 0 ∣ b 1 = b 1 \lvert f_1\rvert= \lvert f_0\rvert b_1 = b_1 ∣ f 1 ∣ = ∣ f 0 ∣ b 1 = b 1 .
Now suppose the claim holds for j − 1 j - 1 j − 1 and j j j , where 1 ≤ j ≤ k − 2 1 \le j \le k - 2 1 ≤ j ≤ k − 2 . We show it for j + 1 j + 1 j + 1 , using the recurrence in Proposition A.21 (with a j = a ~ j a_j = \tilde{a}_j a j = a ~ j , b j = b ~ j b_j = \tilde{b}_j b j = b ~ j by Proposition A.22):
f j + 1 ( J ) e 1 = ( J − a j I ) f j ( J ) e 1 − b j 2 f j − 1 ( J ) e 1 = ∣ f j ∣ J e j + 1 − a j ∣ f j ∣ e j + 1 − b j 2 ∣ f j − 1 ∣ e j = ∣ f j ∣ J e j + 1 − a j ∣ f j ∣ e j + 1 − b j ∣ f j ∣ e j , \begin{aligned}
f_{j+1}(J)e_1 = (J-a_jI)f_j(J)e_1-b_j^2f_{j-1}(J)e_1 \\
&= \lvert f_j\rvert Je_{j+1}-a_j\lvert f_j\rvert e_{j+1}-b_j^2\lvert f_{j-1}\rvert e_j \\
&= \lvert f_j\rvert Je_{j+1}-a_j\lvert f_j\rvert e_{j+1}-b_j\lvert f_j\rvert e_j,
\end{aligned} f j + 1 ( J ) e 1 = ( J − a j I ) f j ( J ) e 1 − b j 2 f j − 1 ( J ) e 1 = ∣ f j ∣ J e j + 1 − a j ∣ f j ∣ e j + 1 − b j 2 ∣ f j − 1 ∣ e j = ∣ f j ∣ J e j + 1 − a j ∣ f j ∣ e j + 1 − b j ∣ f j ∣ e j ,
since b j ∣ f j − 1 ∣ = ∣ f j ∣ b_j\lvert f_{j-1}\rvert= \lvert f_j\rvert b j ∣ f j − 1 ∣ = ∣ f j ∣ . We read off the ( j + 1 ) (j+1) ( j + 1 ) -th column from the definition of J J J :
J e j + 1 = b j e j + a j e j + 1 + b j + 1 e j + 2 Je_{j+1}=b_je_j+a_je_{j+1}+b_{j+1}e_{j+2} J e j + 1 = b j e j + a j e j + 1 + b j + 1 e j + 2
So the e j e_j e j and e j + 1 e_{j+1} e j + 1 terms cancel out:
f j + 1 ( J ) e 1 = b j + 1 ∣ f j ∣ e j + 2 = ∣ f j + 1 ∣ e j + 2 f_{j+1}(J)e_1=b_{j+1}\lvert f_j\rvert e_{j+2}=\lvert f_{j+1}\rvert e_{j+2} f j + 1 ( J ) e 1 = b j + 1 ∣ f j ∣ e j + 2 = ∣ f j + 1 ∣ e j + 2
The range of indices is valid because j + 2 ≤ k j + 2 \le k j + 2 ≤ k , and at j = k − 2 j = k - 2 j = k − 2 , b j + 1 = b k − 1 b_{j+1} = b_{k-1} b j + 1 = b k − 1 is defined. □
Remark. Note that the proof above touches the columns 1 , … , k − 1 1,\ldots,k-1 1 , … , k − 1 of J J J , so only uses quantities that are known (given) from the desired moments, and did not involve ξ \xi ξ at all. Furthermore, the proof of the lemma above is purely algebraic (cancellation of terms from the recurrence formula), so it holds regardless of ξ \xi ξ and any admissibility.
The remark above is important because the definition of inner product (and therefore ∣ f j ∣ \lvert f_j\rvert ∣ f j ∣ ) itself depends on the probability measure we are using. Up until now, all the inner products have been defined using the given moments m 0 , … , m 2 k − 2 m_0,\ldots,m_{2k-2} m 0 , … , m 2 k − 2 , therefore using ν ~ \tilde{\nu} ν ~ . Now consider any i , j i,j i , j . If i ≠ j i \ne j i = j then ⟨ f i , f j ⟩ = 0 \langle f_i,f_j\rangle= 0 ⟨ f i , f j ⟩ = 0 . But if i = j i=j i = j , the inner product is a scalar ∣ f i ∣ 2 \lvert f_i\rvert^2 ∣ f i ∣ 2 . The proposition below shows that under ν ξ \nu_\xi ν ξ , the same result also holds.
Proposition A.25. Under the probability measure ν ξ \nu_\xi ν ξ , we can define ⟨ ⋅ , ⋅ ⟩ ν ξ \langle\cdot,\cdot\rangle_{\nu_\xi} ⟨ ⋅ , ⋅ ⟩ ν ξ the same way. Under this measure,
⟨ f i , f j ⟩ ν ξ = δ i j ∣ f i ∣ 2 \langle f_i,f_j\rangle_{\nu_\xi}=\delta_{ij}\lvert f_i\rvert^2 ⟨ f i , f j ⟩ ν ξ = δ ij ∣ f i ∣ 2 where the norm on the RHS is taken under the original probability measure ν ~ \tilde{\nu} ν ~
Proof. Take any polynomial g ( x ) = ∑ d c d x d g(x)=\sum_d c_dx^d g ( x ) = ∑ d c d x d . Now consider the moment E ν ξ [ g ( s 2 ) ] \mathbb{E}_{\nu_\xi}\left[g(s^2)\right] E ν ξ [ g ( s 2 ) ] under ν ξ \nu_\xi ν ξ . From the proof of Proposition A.23 ,
E ν ξ [ s 2 d ] = ( J d ) 1 , 1 \mathbb{E}_{\nu_\xi}\left[s^{2d}\right]=(J^d)_{1,1} E ν ξ [ s 2 d ] = ( J d ) 1 , 1
So,
E ν ξ [ g ( s 2 ) ] = ∑ d c d ( J d ) 1 , 1 = g ( J ) 1 , 1 = e 1 T g ( J ) e 1 \mathbb{E}_{\nu_\xi}\left[g(s^2)\right]=\sum_d c_d(J^d)_{1,1}=g(J)_{1,1}=e_1^Tg(J)e_1 E ν ξ [ g ( s 2 ) ] = d ∑ c d ( J d ) 1 , 1 = g ( J ) 1 , 1 = e 1 T g ( J ) e 1
Now apply it with g ( x ) = f i ( x ) f j ( x ) g(x)=f_i(x)f_j(x) g ( x ) = f i ( x ) f j ( x ) , and note that the inner product under ν ξ \nu_\xi ν ξ is exactly the expected value of the product of these two polynomials.
⟨ f i , f j ⟩ ν ξ = E ν ξ [ f i ( s 2 ) f j ( s 2 ) ] = E ν ξ [ g ( s 2 ) ] = e 1 T g ( J ) e 1 \langle f_i,f_j\rangle_{\nu_\xi}=\mathbb{E}_{\nu_\xi}\left[f_i(s^2)f_j(s^2)\right]=\mathbb{E}_{\nu_\xi}\left[g(s^2)\right]=e_1^{T}g(J)e_1 ⟨ f i , f j ⟩ ν ξ = E ν ξ [ f i ( s 2 ) f j ( s 2 ) ] = E ν ξ [ g ( s 2 ) ] = e 1 T g ( J ) e 1
But now because J J J is symmetric, then powers of J J J are symmetric too, so:
L H S = [ f i ( J ) e 1 ] T [ f j ( J ) e 1 ] LHS=[f_i(J)e_1]^T[f_j(J)e_1] L H S = [ f i ( J ) e 1 ] T [ f j ( J ) e 1 ]
And now apply Lemma A.24 to both factors and multiply:
L H S = ∣ f i ∣ ∣ f j ∣ e i + 1 T e j + 1 = R H S LHS=\lvert f_i\rvert\lvert f_j\rvert e_{i+1}^{T}e_{j+1}=RHS L H S = ∣ f i ∣ ∣ f j ∣ e i + 1 T e j + 1 = R H S
The lemma is a purely algebraic proof, no probability measure involved, as we have remarked. But all the norms are defined using the reference measure ν ~ \widetilde{\nu} ν , so the RHS in this proposition is also defined using the reference measure.
Since m d = ⟨ x a , x b ⟩ m_d=\langle x^a,x^b\rangle m d = ⟨ x a , x b ⟩ for any a + b = d a+b=d a + b = d , and we matched the inner product of the basis under both probability measures ν ~ \widetilde{\nu} ν and ν ξ \nu_\xi ν ξ , then we also matched m d m_d m d under both measures. Note that this applies to a , b ≤ k − 1 a,b\le k-1 a , b ≤ k − 1 so for d ≤ 2 k − 2 d\le2k-2 d ≤ 2 k − 2 , which are exactly the moments we are asked to match. In fact, m 2 k − 2 m_{2k-2} m 2 k − 2 is the bottom-right corner of the matrix M k M_k M k , the “last” element in the matrix that we needed to match.
However, we can push the computation one “index” higher and compute m 2 k − 1 m_{2k-1} m 2 k − 1 , or better yet, compute ⟨ x f k − 1 , f k − 1 ⟩ \langle xf_{k-1},f_{k-1}\rangle ⟨ x f k − 1 , f k − 1 ⟩ two ways, one of which will contain E [ x 2 k − 1 ] \mathbb{E}\left[x^{2k-1}\right] E [ x 2 k − 1 ] and the other way will draw from J J J .
First, by definition of a k − 1 a_{k-1} a k − 1 :
⟨ x f k − 1 , f k − 1 ⟩ ν ξ = a k − 1 ∣ f k − 1 ∣ 2 \langle xf_{k-1},f_{k-1}\rangle_{\nu_\xi}=a_{k-1}\lvert f_{k-1}\rvert^2 ⟨ x f k − 1 , f k − 1 ⟩ ν ξ = a k − 1 ∣ f k − 1 ∣ 2
Second, applying Lemma A.24 :
⟨ x f k − 1 , f k − 1 ⟩ ν ξ = ( x f k − 1 2 ) ( J ) 1 , 1 = [ f k − 1 ( J ) e 1 ] T ⋅ J ⋅ [ f k − 1 ( J ) e 1 ] = [ ∣ f k − 1 ∣ e k ] T ⋅ J ⋅ [ ∣ f k − 1 ∣ e k ] = ∣ f k − 1 ∣ 2 J k , k = ξ ∣ f k − 1 ∣ 2 \begin{aligned}
\langle xf_{k-1},f_{k-1}\rangle_{\nu_\xi}=(xf_{k-1}^2)(J)_{1,1}=[f_{k-1}(J)e_1]^T\cdot J\cdot[f_{k-1}(J)e_1] \\
&=[\lvert f_{k-1}\rvert e_k]^T\cdot J\cdot[\lvert f_{k-1}\rvert e_k]=\lvert f_{k-1}\rvert^2J_{k,k}=\xi\lvert f_{k-1}\rvert^2
\end{aligned} ⟨ x f k − 1 , f k − 1 ⟩ ν ξ = ( x f k − 1 2 ) ( J ) 1 , 1 = [ f k − 1 ( J ) e 1 ] T ⋅ J ⋅ [ f k − 1 ( J ) e 1 ] = [∣ f k − 1 ∣ e k ] T ⋅ J ⋅ [∣ f k − 1 ∣ e k ] = ∣ f k − 1 ∣ 2 J k , k = ξ ∣ f k − 1 ∣ 2
So a k − 1 = ξ a_{k-1}=\xi a k − 1 = ξ . Note that this quantity contains m 2 k − 1 m_{2k-1} m 2 k − 1 as its leading coefficient: expanding ⟨ x f k − 1 , f k − 1 ⟩ ν ξ = m 2 k − 1 ( ν ξ ) + ( terms in m 0 , … , m 2 k − 2 ) \langle xf_{k-1},f_{k-1}\rangle_{\nu_\xi}=m_{2k-1}(\nu_\xi)+(\text{terms in }m_0,\ldots,m_{2k-2}) ⟨ x f k − 1 , f k − 1 ⟩ ν ξ = m 2 k − 1 ( ν ξ ) + ( terms in m 0 , … , m 2 k − 2 ) , and the lower terms are matched. So m 2 k − 1 ( ν ξ ) = ∣ f k − 1 ∣ 2 ξ + c m_{2k-1}(\nu_\xi)=\lvert f_{k-1}\rvert^2\xi+c m 2 k − 1 ( ν ξ ) = ∣ f k − 1 ∣ 2 ξ + c for a constant c c c determined by the data, an affine function of ξ \xi ξ with positive slope ∣ f k − 1 ∣ 2 \lvert f_{k-1}\rvert^2 ∣ f k − 1 ∣ 2 . However, ξ \xi ξ is precisely what generates the configuration Θ \Theta Θ . In other words, the configuration matches exactly the moments that were given to us, and not more. The first moment that we are not required to match is in fact free and varies by ξ \xi ξ .
Corollary A.26 (Moment matching and first unmatched moment). Suppose ξ 1 ≠ ξ 2 \xi_1\ne\xi_2 ξ 1 = ξ 2 generate Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 with the construction defined in Definition A.19 . Then the moments m 0 , … , m 2 k − 2 m_0,\ldots,m_{2k-2} m 0 , … , m 2 k − 2 of Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 are equal, i.e. Θ 1 ∼ 2 k − 1 o Θ 2 \Theta_1\sim^o_{2k-1}\Theta_2 Θ 1 ∼ 2 k − 1 o Θ 2 . However, m 2 k − 1 m_{2k-1} m 2 k − 1 are different. In fact, m 2 k − 1 ( ν ξ ) = ∣ f k − 1 ∣ 2 ξ + c m_{2k-1}(\nu_\xi)=\lvert f_{k-1}\rvert^2\xi+c m 2 k − 1 ( ν ξ ) = ∣ f k − 1 ∣ 2 ξ + c is strictly increasing and affine in ξ \xi ξ . In terms of K = 2 k K=2k K = 2 k : the matched moments are m 0 , … , m K − 2 m_0,\ldots,m_{K-2} m 0 , … , m K − 2 and the first unmatched moment m K − 1 m_{K-1} m K − 1 is strictly increasing in ξ \xi ξ .
Proof. The moments m 0 , … , m 2 k − 2 m_0,\ldots,m_{2k-2} m 0 , … , m 2 k − 2 match by Proposition A.25 and the paragraph after it. For m 2 k − 1 m_{2k-1} m 2 k − 1 , the computation above gives ⟨ x f k − 1 , f k − 1 ⟩ ν ξ = ξ ∣ f k − 1 ∣ 2 \langle xf_{k-1},f_{k-1}\rangle_{\nu_\xi}=\xi\lvert f_{k-1}\rvert^2 ⟨ x f k − 1 , f k − 1 ⟩ ν ξ = ξ ∣ f k − 1 ∣ 2 . Expanding the left side, the coefficient of m 2 k − 1 ( ν ξ ) m_{2k-1}(\nu_\xi) m 2 k − 1 ( ν ξ ) is one and every other term involves only m 0 , … , m 2 k − 2 m_0,\ldots,m_{2k-2} m 0 , … , m 2 k − 2 , which are matched. So m 2 k − 1 ( ν ξ ) = ∣ f k − 1 ∣ 2 ξ + c m_{2k-1}(\nu_\xi)=\lvert f_{k-1}\rvert^2\xi+c m 2 k − 1 ( ν ξ ) = ∣ f k − 1 ∣ 2 ξ + c , and the slope ∣ f k − 1 ∣ 2 \lvert f_{k-1}\rvert^2 ∣ f k − 1 ∣ 2 is positive.
Corollary A.27 (Uniqueness of construction). Let Θ \Theta Θ be any configuration with K = 2 k K = 2k K = 2 k communities and probability measure ν Θ \nu_{\Theta} ν Θ , such that m d m_d m d under ν Θ \nu_{\Theta} ν Θ match for 0 ≤ d ≤ 2 k − 2 0 \le d \le2k - 2 0 ≤ d ≤ 2 k − 2 . Then ν Θ = ν ξ \nu_{\Theta} = \nu_{\xi} ν Θ = ν ξ for some ξ \xi ξ . In other words, Θ \Theta Θ must have been constructed using the procedure in Definition A.19 .
Proof. Because the moments are the same up to 2 k − 2 2k - 2 2 k − 2 , the M \mathbf{M} M matrices are the same, and hence the factors U U U are the same, and hence f j f_j f j (due to uniqueness of monic orthogonal family). In fact, we simply apply the Gram–Schmidt process which is deterministic and well-defined. Then all the coefficients a j , b j a_j, b_j a j , b j are the same too. The only free choice left is the corner ξ = a k − 1 \xi= a_{k-1} ξ = a k − 1 , and it is well defined because ν Θ \nu_{\Theta} ν Θ is an actual measure so it has its own m 2 k − 1 m_{2k-1} m 2 k − 1 . It remains to see that ν Θ \nu_{\Theta} ν Θ is determined by this matrix. Since Θ \Theta Θ has K = 2 k K = 2k K = 2 k communities, ν Θ \nu_{\Theta} ν Θ has exactly k k k atoms, so it is the spectral measure at e 1 e_1 e 1 of its own k × k k \times k k × k Jacobi matrix [20 Section 1.3] . That matrix is J ( ξ ) J(\xi) J ( ξ ) with ξ = a ~ k − 1 ( ν Θ ) \xi= \widetilde{a}_{k-1}(\nu_{\Theta}) ξ = a k − 1 ( ν Θ ) , so ν Θ = ν ξ \nu_{\Theta} = \nu_{\xi} ν Θ = ν ξ by the identity E ν ξ [ s 2 d ] = ( J d ) 1 , 1 E_{\nu_{\xi}}[s^{2d}] = (J^d)_{1,1} E ν ξ [ s 2 d ] = ( J d ) 1 , 1 in the proof of Proposition A.23 .
The following proposition is not needed for the proof but it provides an insight into why the matrix J J J is the way it is. The inspiration for this construction was taken from truncated Stieltjes moment problem. Note that by definition of U U U , it is a change of basis from M \mathbf{M} M ’s native coordinate to its orthonormal coordinate, so in its orthonormal coordinate M \mathbf{M} M is an identity matrix. Indeed U − T M U − 1 = I U^{-T}\mathbf{M}U^{-1} = I U − T M U − 1 = I . The following proposition shows that J J J is the “shifted-by-1” moment matrix in the orthonormal coordinate. The shifting of moment matrix by 1 is the standard technique used in many moment problem solution.
Proposition A.28. Let M ( 1 ) \mathbf{M}^{(1)} M ( 1 ) be the shifted-by-1 moment matrix, that is M a , b ( 1 ) = m ( a − 1 ) + ( b − 1 ) + 1 = m a + b − 1 \mathbf{M}^{(1)}_{a,b} = m_{(a-1)+(b-1)+1} = m_{a+b-1} M a , b ( 1 ) = m ( a − 1 ) + ( b − 1 ) + 1 = m a + b − 1 instead of m a + b − 2 m_{a+b-2} m a + b − 2 . Then
U − T M ( 1 ) U − 1 = J ( ξ r e f ) , ξ r e f = a ~ k − 1 ( ν ~ ) U^{-T}\mathbf{M}^{(1)}U^{-1} = J(\xi_{\mathrm{ref}}), \qquad\xi_{\mathrm{ref}} = \widetilde{a}_{k-1}(\widetilde{\nu}) U − T M ( 1 ) U − 1 = J ( ξ ref ) , ξ ref = a k − 1 ( ν )
Proof. M a , b ( 1 ) = m a + b − 1 = ⟨ x a − 1 , x ⋅ x b − 1 ⟩ \mathbf{M}^{(1)}_{a,b} = m_{a+b-1} = \langle x^{a-1}, x \cdot x^{b-1}\rangle M a , b ( 1 ) = m a + b − 1 = ⟨ x a − 1 , x ⋅ x b − 1 ⟩ . Similar to the proof of Proposition A.22, expand x a − 1 = ∑ i U i , a p i − 1 x^{a-1} = \sum_i U_{i,a}p_{i-1} x a − 1 = ∑ i U i , a p i − 1 and x ⋅ x b − 1 = ∑ j U j , b x p j − 1 x \cdot x^{b-1} = \sum_j U_{j,b}x p_{j-1} x ⋅ x b − 1 = ∑ j U j , b x p j − 1 , substitute and use the linearity of the inner product, so
M a , b ( 1 ) = ∑ i , j U i , a ⟨ p i − 1 , x p j − 1 ⟩ U j , b = ( U T J U ) a , b \mathbf{M}^{(1)}_{a,b} = \sum_{i,j} U_{i,a}\langle p_{i-1}, x p_{j-1}\rangle U_{j,b} = (U^TJU)_{a,b} M a , b ( 1 ) = i , j ∑ U i , a ⟨ p i − 1 , x p j − 1 ⟩ U j , b = ( U T J U ) a , b
The last equality can be gleaned from the definition of J J J . On the main diagonal, the entries are a i − 1 = ⟨ p i − 1 , x p i − 1 ⟩ a_{i-1} = \langle p_{i-1}, x p_{i-1}\rangle a i − 1 = ⟨ p i − 1 , x p i − 1 ⟩ . On the diagonal above the main diagonal, the entries are
⟨ p i − 1 , x p i ⟩ = ⟨ x p i − 1 , p i ⟩ = ⟨ x f i − 1 , f i ⟩ ∣ f i − 1 ∣ ∣ f i ∣ \langle p_{i-1}, xp_i\rangle= \langle xp_{i-1}, p_i\rangle= \frac{\langle xf_{i-1}, f_i\rangle}{|f_{i-1}||f_i|} ⟨ p i − 1 , x p i ⟩ = ⟨ x p i − 1 , p i ⟩ = ∣ f i − 1 ∣∣ f i ∣ ⟨ x f i − 1 , f i ⟩
But note that x f i − 1 xf_{i-1} x f i − 1 is a monic polynomial with degree i i i , so it can be expressed as f i + ⋯ f_i + \cdots f i + ⋯ where the rest of the terms are lower degree. So upon taking inner product with f i f_i f i , only the first term survives, so the entry becomes ⟨ f i , f i ⟩ ∣ f i − 1 ∣ ∣ f i ∣ = b i \frac{\langle f_i,f_i\rangle}{|f_{i-1}||f_i|} = b_i ∣ f i − 1 ∣∣ f i ∣ ⟨ f i , f i ⟩ = b i . The entries below the main diagonal are proven the same way.
Remark. Two consequences from the proof of this proposition, both explain why J J J has that particular structure. First, J J J is tridiagonal because if ∣ i − j ∣ > 1 |i-j| > 1 ∣ i − j ∣ > 1 then nothing survives the inner product ⟨ p i − 1 , x p j − 1 ⟩ \langle p_{i-1},x p_{j-1}\rangle ⟨ p i − 1 , x p j − 1 ⟩ . Second, all the entries of M \mathbf{M} M have been determined by the data (or given to be matched), but when we shift by 1, the bottom-right corner of M ( 1 ) \mathbf{M}^{(1)} M ( 1 ) is free. Because U U U is upper triangular, transforming this matrix to and from J J J means the bottom-right corner of J J J remains free, and that is where we get to choose ξ \xi ξ .
Imagine if an oracle gives us the next moment m 2 k − 1 m_{2k-1} m 2 k − 1 instead, then one can apply this procedure to find a ξ \xi ξ that would realize that moment. This ξ \xi ξ always exists and the resulting configuration is structurally admissible. Whether or not it is admissible in the greater sense (dot products always in [ 0 , 1 ] [0,1] [ 0 , 1 ] etc) is a different issue. The entire machinery in this subsection is algebraic and linear-algebraic. In a way, the fiber can be thought of as the list of configurations that realizes all possible m 2 k − 1 m_{2k-1} m 2 k − 1 moments, truncated in order to guarantee admissibility.
Remark. To summarize the construction, we are given Gram matrix M \mathrm{M} M , and U U U is the basis change that makes it orthonormal in the space induced by the bilinear form. One can show that J J J is the shifted Gram matrix in this coordinate system. The data can fill M \mathrm{M} M completely, and it can fill the shifted M ( 1 ) \mathrm{M}^{(1)} M ( 1 ) almost everywhere except its last corner. This freedom in the last corner is what generates the fiber. The matrix J J J that we gave in closed form is merely this shifted matrix in the orthonormal coordinate. All the coefficients a j , b j a_j,b_j a j , b j are merely entries of the basis change matrix U U U . These techniques are all known (Krein’s canonical representations [27 ] ; the Gauss–Radau rule as a modification of the last diagonal entry of the Jacobi matrix [21 ] , with nodes and weights from its eigenpairs [23 ] ; and the one-parameter family of k k k -point rules of degree 2 k − 2 2k-2 2 k − 2 , whose node polynomials f k + c f k − 1 f_k+c f_{k-1} f k + c f k − 1 are quasi-orthogonal [46 ] ). Our contribution is reducing the problem of matching submotif densities into truncated moment problem.
Admissibility Analysis
In Proposition A.23 we showed that for any ξ \xi ξ , the resulting lines are all distinct, the community weights are all positive and sum up to 1. However, we still need to prove 1) that different ξ \xi ξ will give different configurations, 2) identify the range allowed so that the resulting dot product will be in the interval [ 0 , 1 ] [0,1] [ 0 , 1 ] , and 3) identify the range allowed so that the eigenvalues are positive.
Monotonicity
Proposition A.29 (Monotone Transport). Each eigenvalue t i ( ξ ) t_i(\xi) t i ( ξ ) is a continuously differentiable, strictly increasing function of ξ \xi ξ , with
d t i d ξ = ( v i ) k 2 > 0 , ∑ i = 1 k d t i d ξ = 1. \frac{d t_i}{d \xi}=(v_i)_k^2>0,\qquad\sum_{i=1}^{k}\frac{d t_i}{d \xi}=1. d ξ d t i = ( v i ) k 2 > 0 , i = 1 ∑ k d ξ d t i = 1. Consequently ξ 1 − ξ 2 = ∑ i = 1 k ( t i ( ξ 1 ) − t i ( ξ 2 ) ) \xi_1-\xi_2=\sum_{i=1}^{k}(t_i(\xi_1)-t_i(\xi_2)) ξ 1 − ξ 2 = ∑ i = 1 k ( t i ( ξ 1 ) − t i ( ξ 2 )) , and different ξ \xi ξ give different configurations. Moreover t k ( ξ ) ≤ ξ ≤ t 1 ( ξ ) t_k(\xi)\leq\xi\leq t_1(\xi) t k ( ξ ) ≤ ξ ≤ t 1 ( ξ ) .
Proof. The eigenvalues are simple (Proposition A.23), hence differentiable in ξ \xi ξ with derivative given by the Hellmann–Feynman formula. Since ∂ ∂ ξ J = e k e k T \frac{\partial}{\partial\xi}J=e_ke_k^{T} ∂ ξ ∂ J = e k e k T ,
d t i d ξ = v i T e k e k T v i = ( v i ) k 2 . \frac{d t_i}{d \xi}=v_i^{T}e_ke_k^{T}v_i=(v_i)_k^2. d ξ d t i = v i T e k e k T v i = ( v i ) k 2 .
This is nonzero: reading the rows of ( J − λ I ) v = 0 (J-\lambda I)v=0 ( J − λ I ) v = 0 from the bottom, row k k k gives b k − 1 v k − 1 = ( λ − ξ ) v k b_{k-1}v_{k-1}=(\lambda-\xi)v_k b k − 1 v k − 1 = ( λ − ξ ) v k , so v k = 0 v_k=0 v k = 0 forces v k − 1 = 0 v_{k-1}=0 v k − 1 = 0 , then row k − 1 k-1 k − 1 forces v k − 2 = 0 v_{k-2}=0 v k − 2 = 0 , and so on, giving v = 0 v=0 v = 0 . The sum is ∑ i ( v i ) k 2 = 1 \sum_i(v_i)_k^2=1 ∑ i ( v i ) k 2 = 1 , the squared norm of row k k k of the orthogonal matrix V V V . (Equivalently, ∑ i t i = tr J ( ξ ) = ∑ j = 0 k − 2 a j + ξ \sum_i t_i=\operatorname{tr}J(\xi)=\sum_{j=0}^{k-2}a_j+\xi ∑ i t i = tr J ( ξ ) = ∑ j = 0 k − 2 a j + ξ .) Integrating gives the displayed identity. Finally, t k ≤ e k T J e k = ξ ≤ t 1 t_k\leq e_k^TJe_k=\xi\leq t_1 t k ≤ e k T J e k = ξ ≤ t 1 by the Rayleigh quotient. □ \square □
Range of ξ \xi ξ . Recall that for each pair of nodes u , v u,v u , v belonging to communities i , j i,j i , j , W ( u , v ) = x 1 , u x 1 , v ( 1 + s i s j ) W(u,v)=x_{1,u}x_{1,v}(1+s_i s_j) W ( u , v ) = x 1 , u x 1 , v ( 1 + s i s j ) with x 1 , u , x 1 , v ∈ [ 0 , C ] x_{1,u},x_{1,v}\in[0,C] x 1 , u , x 1 , v ∈ [ 0 , C ] . We need that 0 ≤ W ≤ 1 0\le W\le1 0 ≤ W ≤ 1 . First, consider the condition that W ≥ 0 W\ge0 W ≥ 0 . The negative factor can come from ( 1 + s i s j ) (1+s_i s_j) ( 1 + s i s j ) and the smallest value this can take is when i = 1 , j = K i=1,j=K i = 1 , j = K (the outermost two lines). We have 1 + s i s j = 1 − s 1 2 = 1 − t 1 ≥ 0 1+s_i s_j=1-s_1^2=1-t_1\ge0 1 + s i s j = 1 − s 1 2 = 1 − t 1 ≥ 0 so we need t 1 ≤ 1 t_1\le1 t 1 ≤ 1 .
Next consider the condition W ≤ 1 W\le1 W ≤ 1 . The maximum value W W W can achieve is when both points are sampled from the farthest possible distance radially, and that i = j = 1 i=j=1 i = j = 1 , so C 2 ( 1 + t 1 ) ≤ 1 C^2(1+t_1)\le1 C 2 ( 1 + t 1 ) ≤ 1 so t 1 ≤ 1 / C 2 − 1 t_1\le1/C^2-1 t 1 ≤ 1/ C 2 − 1 . So we need t 1 ≤ T = min ( 1 , 1 / C 2 − 1 ) t_1\le T=\min(1,1/C^2-1) t 1 ≤ T = min ( 1 , 1/ C 2 − 1 ) . Since R R R is supported on the open interval ( 0 , C ) (0,C) ( 0 , C ) , W < 1 W<1 W < 1 strictly even when t 1 = T t_1=T t 1 = T , so the endpoint t 1 = T t_1=T t 1 = T is admissible. Now we will look for the range of ξ \xi ξ such that all eigenvalues are positive and are no greater than T T T .
Lemma A.30 (Characteristic polynomials). Let J j J_j J j be the leading j × j j\times j j × j block of J ( ξ ) J(\xi) J ( ξ ) (independent of ξ \xi ξ for j ≤ k − 1 j\le k-1 j ≤ k − 1 ). Then f j ( x ) = det ( x I − J j ) f_j(x)=\det(xI-J_j) f j ( x ) = det ( x I − J j ) for 1 ≤ j ≤ k − 1 1\le j\le k-1 1 ≤ j ≤ k − 1 , and
P ξ ( x ) : = det ( x I − J ( ξ ) ) = ( x − ξ ) f k − 1 ( x ) − b k − 1 2 f k − 2 ( x ) , P_\xi(x):=\det(xI-J(\xi))=(x-\xi)f_{k-1}(x)-b_{k-1}^2f_{k-2}(x), P ξ ( x ) := det ( x I − J ( ξ )) = ( x − ξ ) f k − 1 ( x ) − b k − 1 2 f k − 2 ( x ) , with the conventions f − 1 : = 0 f_{-1}:=0 f − 1 := 0 and b 0 : = 0 b_0:=0 b 0 := 0 (so P ξ ( x ) = x − ξ P_\xi(x)=x-\xi P ξ ( x ) = x − ξ when k = 1 k=1 k = 1 ).
Proof. Expanding det ( x I − J j + 1 ) \det(xI-J_{j+1}) det ( x I − J j + 1 ) along its last row gives det ( x I − J j + 1 ) = ( x − a j ) det ( x I − J j ) − b j 2 det ( x I − J j − 1 ) \det(xI-J_{j+1})=(x-a_j)\det(xI-J_j)-b_j^2\det(xI-J_{j-1}) det ( x I − J j + 1 ) = ( x − a j ) det ( x I − J j ) − b j 2 det ( x I − J j − 1 ) , with det ( x I − J 0 ) = 1 \det(xI-J_0)=1 det ( x I − J 0 ) = 1 and det ( x I − J 1 ) = x − a 0 = x − m 1 \det(xI-J_1)=x-a_0=x-m_1 det ( x I − J 1 ) = x − a 0 = x − m 1 . This is the recurrence and initial condition of Proposition A.21, with a j = a ~ j a_j=\tilde a_j a j = a ~ j , b j = b ~ j b_j=\tilde b_j b j = b ~ j by Proposition A.22. The same expansion for J ( ξ ) J(\xi) J ( ξ ) , whose last diagonal entry is ξ \xi ξ , gives P ξ P_\xi P ξ . □
Theorem A.31. Let the reference configuration be admissible, let T = min ( 1 , 1 C 2 − 1 ) T=\min\left(1,\frac{1}{C^2}-1\right) T = min ( 1 , C 2 1 − 1 ) , and let
ξ − = − b k − 1 2 f k − 2 ( 0 ) f k − 1 ( 0 ) \xi^-=-\frac{b_{k-1}^2f_{k-2}(0)}{f_{k-1}(0)} ξ − = − f k − 1 ( 0 ) b k − 1 2 f k − 2 ( 0 ) ξ + = T − b k − 1 2 f k − 2 ( T ) f k − 1 ( T ) \xi^+=T-\frac{b_{k-1}^2f_{k-2}(T)}{f_{k-1}(T)} ξ + = T − f k − 1 ( T ) b k − 1 2 f k − 2 ( T ) Then all eigenvalues of J ( ξ ) J(\xi) J ( ξ ) lie in ( 0 , T ] (0,T] ( 0 , T ] (so the configuration is admissible) if and only if ξ ∈ ( ξ − , ξ + ] \xi\in(\xi^-,\xi^+] ξ ∈ ( ξ − , ξ + ] . This interval is nonempty and contains the reference value ξ r e f = a ~ k − 1 ( ν ~ ) \xi_{\mathrm{ref}}=\tilde a_{k-1}(\tilde\nu) ξ ref = a ~ k − 1 ( ν ~ ) . These are the Gauss–Radau rules of ν ~ \tilde\nu ν ~ with a prescribed node at 0 0 0 and at T T T ([21 , 20 , 22 ] ). For k = 1 k=1 k = 1 , ξ − = 0 \xi^-=0 ξ − = 0 and ξ + = T \xi^+=T ξ + = T .
Proof. The case k = 1 k=1 k = 1 is immediate: J ( ξ ) = [ ξ ] J(\xi)=[\xi] J ( ξ ) = [ ξ ] , so t 1 = ξ t_1=\xi t 1 = ξ and the condition is 0 < ξ ≤ T 0<\xi\le T 0 < ξ ≤ T . Assume k ≥ 2 k\ge2 k ≥ 2 .
Step 1 (interlacing). Let J k − 1 J_{k-1} J k − 1 be the leading ( k − 1 ) × ( k − 1 ) (k-1)\times(k-1) ( k − 1 ) × ( k − 1 ) block, which does not depend on ξ \xi ξ . By Lemma A.30 , its eigenvalues θ 1 > ⋯ > θ k − 1 \theta_1>\cdots>\theta_{k-1} θ 1 > ⋯ > θ k − 1 are the zeros of f k − 1 f_{k-1} f k − 1 . Cauchy interlacing gives, for every ξ \xi ξ :
t 1 > θ 1 > t 2 > θ 2 > ⋯ > θ k − 1 > t k . t_1>\theta_1>t_2>\theta_2>\cdots>\theta_{k-1}>t_k. t 1 > θ 1 > t 2 > θ 2 > ⋯ > θ k − 1 > t k . (Strict, because J J J is unreduced.) By Corollary A.27 , the reference measure is ν ~ = ν ξ r e f \tilde\nu=\nu_{\xi_{\mathrm{ref}}} ν ~ = ν ξ ref for some ξ r e f \xi_{\mathrm{ref}} ξ ref , so the interlacing also holds for the reference eigenvalues t ~ 1 > ⋯ > t ~ k \tilde t_1>\cdots>\tilde t_k t ~ 1 > ⋯ > t ~ k . The reference is admissible, so 0 < t ~ k 0<\tilde t_k 0 < t ~ k and t ~ 1 ≤ T \tilde t_1\le T t ~ 1 ≤ T , hence every θ j ∈ ( t ~ k , t ~ 1 ) ⊂ ( 0 , T ) \theta_j\in(\tilde t_k,\tilde t_1)\subset(0,T) θ j ∈ ( t ~ k , t ~ 1 ) ⊂ ( 0 , T ) . Therefore t 2 , … , t k − 1 ∈ ( θ k − 1 , θ 1 ) ⊂ ( 0 , T ) t_2,\ldots,t_{k-1}\in(\theta_{k-1},\theta_1)\subset(0,T) t 2 , … , t k − 1 ∈ ( θ k − 1 , θ 1 ) ⊂ ( 0 , T ) for every ξ \xi ξ : only t 1 t_1 t 1 can exceed T T T and only t k t_k t k can be nonpositive.
Step 2 (monotonicity). By Proposition A.29, t k t_k t k and t 1 t_1 t 1 are continuous and strictly increasing, with t k ( ξ ) ≤ ξ → − ∞ t_k(\xi)\le\xi\to-\infty t k ( ξ ) ≤ ξ → − ∞ as ξ → − ∞ \xi\to-\infty ξ → − ∞ and t 1 ( ξ ) ≥ ξ → ∞ t_1(\xi)\ge\xi\to\infty t 1 ( ξ ) ≥ ξ → ∞ as ξ → ∞ \xi\to\infty ξ → ∞ . Hence { ξ : t k ( ξ ) > 0 } = ( ξ − , ∞ ) \{\xi:t_k(\xi)>0\}=(\xi^-,\infty) { ξ : t k ( ξ ) > 0 } = ( ξ − , ∞ ) where ξ − \xi^- ξ − is the unique solution of t k ( ξ ) = 0 t_k(\xi)=0 t k ( ξ ) = 0 , and { ξ : t 1 ( ξ ) ≤ T } = ( − ∞ , ξ + ] \{\xi:t_1(\xi)\le T\}=(-\infty,\xi^+] { ξ : t 1 ( ξ ) ≤ T } = ( − ∞ , ξ + ] where ξ + \xi^+ ξ + is the unique solution of t 1 ( ξ ) = T t_1(\xi)=T t 1 ( ξ ) = T . The admissible set is their intersection ( ξ − , ξ + ] (\xi^-,\xi^+] ( ξ − , ξ + ] .
Step 3 (closed form). By Lemma A.30 , a number a a a is an eigenvalue of J ( ξ ) J(\xi) J ( ξ ) if and only if P ξ ( a ) = 0 P_{\xi}(a)=0 P ξ ( a ) = 0 . When f k − 1 ( a ) ≠ 0 f_{k-1}(a)\ne0 f k − 1 ( a ) = 0 this is equivalent to
ξ = ξ ( a ) : = a − b k − 1 2 f k − 2 ( a ) f k − 1 ( a ) . \xi=\xi(a):=a-\frac{b_{k-1}^{2}f_{k-2}(a)}{f_{k-1}(a)}. ξ = ξ ( a ) := a − f k − 1 ( a ) b k − 1 2 f k − 2 ( a ) .
This is well defined at a = 0 a=0 a = 0 and a = T a=T a = T because the zeros θ j \theta_j θ j of f k − 1 f_{k-1} f k − 1 lie in ( 0 , T ) (0,T) ( 0 , T ) . At ξ = ξ ( 0 ) \xi=\xi(0) ξ = ξ ( 0 ) , the eigenvalue 0 0 0 must be t k t_k t k , since t 1 , … , t k − 1 > θ k − 1 > 0 t_1,\ldots,t_{k-1}>\theta_{k-1}>0 t 1 , … , t k − 1 > θ k − 1 > 0 ; so ξ − = ξ ( 0 ) \xi^-=\xi(0) ξ − = ξ ( 0 ) . At ξ = ξ ( T ) \xi=\xi(T) ξ = ξ ( T ) , the eigenvalue T T T must be t 1 t_1 t 1 , since t 2 , … , t k < θ 1 < T t_2,\ldots,t_k<\theta_1<T t 2 , … , t k < θ 1 < T ; so ξ + = ξ ( T ) \xi^+=\xi(T) ξ + = ξ ( T ) . This gives the stated formulas.
Step 4 (nonempty). The reference is admissible, so ξ r e f ∈ ( ξ − , ξ + ] \xi_{\mathrm{ref}}\in(\xi^-,\xi^+] ξ ref ∈ ( ξ − , ξ + ] . By the computation preceding Corollary A.26 , ξ r e f = a ~ k − 1 ( ν ~ ) \xi_{\mathrm{ref}}=\widetilde a_{k-1}(\widetilde\nu) ξ ref = a k − 1 ( ν ) .
Construction for K K K odd
For K = 2 k + 1 K=2k+1 K = 2 k + 1 , the symmetry condition requires that s k + 1 = 0 s_{k+1}=0 s k + 1 = 0 . Just like in the even K K K case, we still would like to match m 0 = 1 , m 1 , … , m K − 2 = m 2 k − 1 m_0=1,m_1,\ldots,m_{K-2}=m_{2k-1} m 0 = 1 , m 1 , … , m K − 2 = m 2 k − 1 . We will attempt a very similar construction as in Definition A.19 and prove correctness and admissibility. The main insight still mimics that of Proposition A.28 , but we scale the entire matrix M M M (and therefore M ( 1 ) M^{(1)} M ( 1 ) ) so that the mean m 1 m_1 m 1 matches. The structural admissibility (Proposition A.23 ) follows by construction.
Definition A.32. Set m d ′ = m d + 1 m 1 m'_d=\frac{m_{d+1}}{m_1} m d ′ = m 1 m d + 1 , 0 ≤ d ≤ 2 k − 2 0\le d\le2k-2 0 ≤ d ≤ 2 k − 2 (this uses m 1 , … , m 2 k − 1 m_1,\ldots,m_{2k-1} m 1 , … , m 2 k − 1 ). Apply Definition A.19 to ( m 0 ′ , … , m 2 k − 2 ′ ) (m'_0,\ldots,m'_{2k-2}) ( m 0 ′ , … , m 2 k − 2 ′ ) . Denote the resulting coefficients, polynomials and matrix by a j ′ a'_j a j ′ , b j ′ b'_j b j ′ , f j ′ f'_j f j ′ and J ′ ( ξ ) J'(\xi) J ′ ( ξ ) , its eigenvalues by t 1 ′ > ⋯ > t k ′ t'_1>\cdots>t'_k t 1 ′ > ⋯ > t k ′ and its orthonormal eigenvectors by v 1 ′ , … , v k ′ v'_1,\ldots,v'_k v 1 ′ , … , v k ′ . Let ν ξ ′ : = ∑ i = 1 k ( v i ′ ) 1 2 δ t i ′ \nu'_{\xi}:=\sum_{i=1}^k(v'_i)^2_1\delta_{t'_i} ν ξ ′ := ∑ i = 1 k ( v i ′ ) 1 2 δ t i ′ , the law of s 2 s^2 s 2 under that even construction. Assume J ′ ( ξ ) ≻ 0 J'(\xi)\succ0 J ′ ( ξ ) ≻ 0 . The slopes of the configuration are: s i = t i ′ s_i=\sqrt{t'_i} s i = t i ′ for i ≤ k i\le k i ≤ k , s k + 1 = 0 s_{k+1}=0 s k + 1 = 0 , and s i = − s K + 1 − i s_i=-s_{K+1-i} s i = − s K + 1 − i for i > k + 1 i>k+1 i > k + 1 . The community weights are
w i = m 1 2 t i ′ ( v i ′ ) 1 2 w_i=\frac{m_1}{2t'_i}(v'_i)^2_1 w i = 2 t i ′ m 1 ( v i ′ ) 1 2 for i ≤ k i\le k i ≤ k , w i = w K + 1 − i w_i=w_{K+1-i} w i = w K + 1 − i for i > k + 1 i>k+1 i > k + 1 , and
w k + 1 = 1 − ∑ i ≠ k + 1 w i . w_{k+1}=1-\sum_{i\ne k+1}w_i. w k + 1 = 1 − i = k + 1 ∑ w i . Call μ ξ \mu_\xi μ ξ the law of s 2 s^2 s 2 under this configuration: μ ξ = w k + 1 δ 0 + ∑ i = 1 k 2 w i δ t i ′ \mu_\xi=w_{k+1}\delta_0+\sum_{i=1}^k2w_i\delta_{t'_i} μ ξ = w k + 1 δ 0 + ∑ i = 1 k 2 w i δ t i ′ .
We will prove moment matching and structural admissibility by simple scaling argument. The idea is that we construct a K − 1 K-1 K − 1 configuration that matches the “scaled” version of the moments, while leaving some wiggle room for the middle community, whose weight must then be determined in order to make the weights sum up to 1.
Theorem A.33. For every ξ \xi ξ with J ′ ( ξ ) ≻ 0 J'(\xi)\succ0 J ′ ( ξ ) ≻ 0 , the configuration described in Definition A.32 matches the required moments m 0 , … , m 2 k − 1 m_0,\ldots,m_{2k-1} m 0 , … , m 2 k − 1 , its outer weights w i w_i w i (i ≠ k + 1 i\ne k+1 i = k + 1 ) are positive, and its nonzero slopes are distinct. The middle weight w k + 1 w_{k+1} w k + 1 is not automatically positive; see Section A.3.1.
Proof. For d = 0 d=0 d = 0 , m 0 ( μ ξ ) = 1 m_0(\mu_\xi)=1 m 0 ( μ ξ ) = 1 by the definition of w k + 1 w_{k+1} w k + 1 . For 1 ≤ d ≤ 2 k − 1 1\le d\le2k-1 1 ≤ d ≤ 2 k − 1 , the middle community contributes 0 d = 0 0^d=0 0 d = 0 , so
m d ( μ ξ ) = ∑ i = 1 k 2 w i ( t i ′ ) d = m 1 ∑ i = 1 k ( v i ′ ) 1 2 ( t i ′ ) d − 1 = m 1 m d − 1 ′ ( ν ξ ′ ) . m_d(\mu_\xi)=\sum_{i=1}^{k}2w_i(t'_i)^d=m_1\sum_{i=1}^{k}(v'_i)^2_1(t'_i)^{d-1}=m_1m'_{d-1}(\nu'_\xi). m d ( μ ξ ) = i = 1 ∑ k 2 w i ( t i ′ ) d = m 1 i = 1 ∑ k ( v i ′ ) 1 2 ( t i ′ ) d − 1 = m 1 m d − 1 ′ ( ν ξ ′ ) .
Since d − 1 ≤ 2 k − 2 d-1 \le2k-2 d − 1 ≤ 2 k − 2 , the even construction matches m d − 1 ′ ( ν ξ ′ ) = m d − 1 ′ m'_{d-1}(\nu'_{\xi})=m'_{d-1} m d − 1 ′ ( ν ξ ′ ) = m d − 1 ′ (Section A.2.1), so m d ( μ ξ ) = m 1 m d − 1 ′ = m d m_d(\mu_{\xi})=m_1m'_{d-1}=m_d m d ( μ ξ ) = m 1 m d − 1 ′ = m d .
Positivity of t i ′ t'_i t i ′ (assumed) and of ( v i ′ ) 1 2 (v'_i)^2_1 ( v i ′ ) 1 2 (Proposition A.23 ) gives w i > 0 w_i>0 w i > 0 for i ≠ k + 1 i\ne k+1 i = k + 1 , and distinctness of the t i ′ t'_i t i ′ gives distinct nonzero slopes. □
Corollary A.34 (First unmatched moment, K K K odd). m 2 k ( μ ξ ) = m 1 m 2 k − 1 ′ ( ν ξ ′ ) = m 1 ( ∣ f k − 1 ′ ∣ 2 ξ + c ′ ) m_{2k}(\mu_{\xi})=m_1m'_{2k-1}(\nu'_{\xi})=m_1(|f'_{k-1}|^2\xi+c') m 2 k ( μ ξ ) = m 1 m 2 k − 1 ′ ( ν ξ ′ ) = m 1 ( ∣ f k − 1 ′ ∣ 2 ξ + c ′ ) for a constant c ′ c' c ′ determined by the data. In terms of K = 2 k + 1 K=2k+1 K = 2 k + 1 : the matched moments are m 0 , … , m K − 2 m_0,\ldots,m_{K-2} m 0 , … , m K − 2 and the first unmatched moment m K − 1 m_{K-1} m K − 1 is strictly increasing and affine in ξ \xi ξ .
Proof. The first equality is the computation above with d = 2 k d=2k d = 2 k . The second is Corollary A.26 applied to the primed construction. □
Admissibility Analysis for K K K odd
The middle ray imposes no new constraint on W W W : within the middle community W = x u x v ≤ C 2 ≤ 1 W=x_u x_v\le C^2\le1 W = x u x v ≤ C 2 ≤ 1 (as T > 0 T>0 T > 0 requires C 2 < 1 C^2<1 C 2 < 1 ), and between the middle and community i i i , 1 + s i ⋅ 0 = 1 ≥ 0 1+s_i\cdot0=1\ge0 1 + s i ⋅ 0 = 1 ≥ 0 . So, as in Section A.2.2, the conditions are 0 < t k ′ 0<t'_k 0 < t k ′ , t 1 ′ ≤ T t'_1\le T t 1 ′ ≤ T , and in addition w k + 1 > 0 w_{k+1}>0 w k + 1 > 0 . We show that the last condition, not t k > 0 t_k>0 t k > 0 , determines the lower endpoint.
Lemma A.35 (Middle weight). If J ′ ( ξ ) ≻ 0 J'(\xi)\succ0 J ′ ( ξ ) ≻ 0 then
w k + 1 = 1 − m 1 g ( ξ ) , g ( ξ ) : = e 1 T J ′ ( ξ ) − 1 e 1 = ∑ i = 1 k ( v i ′ ) 1 2 t i ′ . w_{k+1}=1-m_1g(\xi),\qquad g(\xi):=e_1^T J'(\xi)^{-1}e_1=\sum_{i=1}^{k}\frac{(v'_i)^2_1}{t'_i}. w k + 1 = 1 − m 1 g ( ξ ) , g ( ξ ) := e 1 T J ′ ( ξ ) − 1 e 1 = i = 1 ∑ k t i ′ ( v i ′ ) 1 2 . So w k + 1 > 0 w_{k+1}>0 w k + 1 > 0 if and only if g ( ξ ) < 1 / m 1 g(\xi)<1/m_1 g ( ξ ) < 1/ m 1 .
Proof. ∑ i ≠ k + 1 w i = 2 ∑ i = 1 k m 1 2 t i ′ ( v i ′ ) 1 2 = m 1 ∑ i ( v i ′ ) 1 2 t i ′ \sum_{i\ne k+1}w_i=2\sum_{i=1}^{k}\frac{m_1}{2t'_i}(v'_i)^2_1=m_1\sum_i\frac{(v'_i)^2_1}{t'_i} ∑ i = k + 1 w i = 2 ∑ i = 1 k 2 t i ′ m 1 ( v i ′ ) 1 2 = m 1 ∑ i t i ′ ( v i ′ ) 1 2 , and J ′ − 1 = ∑ i ( t i ′ ) − 1 v i ′ v i ′ T J'^{-1}=\sum_i(t'_i)^{-1}v'_i v_i^{\prime T} J ′ − 1 = ∑ i ( t i ′ ) − 1 v i ′ v i ′ T . □
Proposition A.36. Let ξ 0 ′ : = − b k − 2 ′ 2 f k − 2 ′ ( 0 ) / f k − 1 ′ ( 0 ) \xi'_0:=-b'_{k-2}{}^2f'_{k-2}(0)/f'_{k-1}(0) ξ 0 ′ := − b k − 2 ′ 2 f k − 2 ′ ( 0 ) / f k − 1 ′ ( 0 ) , so that J ′ ( ξ ) ≻ 0 J'(\xi)\succ0 J ′ ( ξ ) ≻ 0 if and only if ξ > ξ 0 ′ \xi>\xi'_0 ξ > ξ 0 ′ (Theorem A.31 , Steps 1–3, applied to the primed construction; its interlacing hypothesis holds by Step 4 of Theorem A.37 below). On ( ξ 0 ′ , ∞ ) (\xi'_0,\infty) ( ξ 0 ′ , ∞ ) , g g g is strictly decreasing, and g ( ξ ) → + ∞ g(\xi)\to+\infty g ( ξ ) → + ∞ as ξ ↓ ξ 0 ′ \xi\downarrow\xi'_0 ξ ↓ ξ 0 ′ .
Proof. Since d d ξ J ′ = e k e k T \frac{d}{d\xi}J'=e_ke_k^T d ξ d J ′ = e k e k T , we have d d ξ J ′ − 1 = − J ′ − 1 e k e k T J ′ − 1 \frac{d}{d\xi}J'^{-1}=-J'^{-1}e_ke_k^TJ'^{-1} d ξ d J ′ − 1 = − J ′ − 1 e k e k T J ′ − 1 , so
g ′ ( ξ ) = − ( ( J ′ − 1 ) 1 k ) 2 . g'(\xi)=-((J'^{-1})_{1k})^2. g ′ ( ξ ) = − (( J ′ − 1 ) 1 k ) 2 .
By the cofactor formula, ( J ′ − 1 ) 1 k = ( − 1 ) k + 1 det ( minor k , 1 ) / det J ′ (J'^{-1})_{1k}=(-1)^{k+1}\det(\operatorname{minor}_{k,1})/\det J' ( J ′ − 1 ) 1 k = ( − 1 ) k + 1 det ( minor k , 1 ) / det J ′ . The minor obtained by deleting row k k k and column 1 1 1 of the tridiagonal J ′ J' J ′ is lower triangular with diagonal b 1 ′ , … , b k − 1 ′ b'_1,\ldots,b'_{k-1} b 1 ′ , … , b k − 1 ′ , so ( J ′ − 1 ) 1 k = ( − 1 ) k + 1 ∏ j = 1 k − 1 b j ′ / det J ′ ≠ 0 (J'^{-1})_{1k}=(-1)^{k+1}\prod_{j=1}^{k-1}b'_j/\det J'\ne0 ( J ′ − 1 ) 1 k = ( − 1 ) k + 1 ∏ j = 1 k − 1 b j ′ / det J ′ = 0 . (For k = 1 k=1 k = 1 , g = 1 / ξ g=1/\xi g = 1/ ξ .) Hence g ′ < 0 g'<0 g ′ < 0 .
For the limit: g ( ξ ) ≥ ( v k ′ ) 1 2 / t k ′ g(\xi)\ge(v'_k)^2_1/t'_k g ( ξ ) ≥ ( v k ′ ) 1 2 / t k ′ . As ξ ↓ ξ 0 ′ \xi\downarrow\xi'_0 ξ ↓ ξ 0 ′ , t k ′ ↓ 0 t'_k\downarrow0 t k ′ ↓ 0 while ( v k ′ ) 1 2 (v'_k)^2_1 ( v k ′ ) 1 2 tends to a positive limit (it is continuous and nonzero at ξ 0 ′ \xi'_0 ξ 0 ′ by Proposition A.23 ), so g → + ∞ g\to+\infty g → + ∞ . □
So w k + 1 → − ∞ w_{k+1}\to-\infty w k + 1 → − ∞ as t k ′ → 0 + t'_k\to0^+ t k ′ → 0 + : the middle weight vanishes strictly before any slope does, and positivity of t k ′ t'_k t k ′ never binds. The next result identifies where it vanishes.
Theorem A.37 (Admissible range, K K K odd). Let K = 2 k + 1 ≥ 3 K=2k+1\ge3 K = 2 k + 1 ≥ 3 and let the reference configuration be admissible. Let α 0 , … , α k − 1 \alpha_0,\ldots,\alpha_{k-1} α 0 , … , α k − 1 be the recurrence coefficients of Proposition A.21 for the reference law of s 2 s^2 s 2 (moments m 0 , … , m 2 k − 1 m_0,\ldots,m_{2k-1} m 0 , … , m 2 k − 1 , all given), and let F k F_k F k be its degree-k k k monic orthogonal polynomial. Set
ξ − = ∑ j = 0 k − 1 α j − ∑ j = 0 k − 2 α j ′ , ξ + = T − b k − 1 ′ 2 f k − 2 ′ ( T ) f k − 1 ′ ( T ) . \xi^-=\sum_{j=0}^{k-1}\alpha_j-\sum_{j=0}^{k-2}\alpha'_j,\qquad\xi^+=T-\frac{b_{k-1}^{\prime\,2}f'_{k-2}(T)}{f'_{k-1}(T)}. ξ − = j = 0 ∑ k − 1 α j − j = 0 ∑ k − 2 α j ′ , ξ + = T − f k − 1 ′ ( T ) b k − 1 ′ 2 f k − 2 ′ ( T ) .
with the conventions of Lemma A.30 (so ξ + = T \xi^{+}=T ξ + = T when k = 1 k=1 k = 1 ). Then the configuration of Definition A.32 is admissible (all t i ′ ∈ ( 0 , T ] t_i' \in(0,T] t i ′ ∈ ( 0 , T ] and w k + 1 > 0 w_{k+1}>0 w k + 1 > 0 ) if and only if ξ ∈ ( ξ − , ξ + ] \xi\in(\xi^{-},\xi^{+}] ξ ∈ ( ξ − , ξ + ] . The interval is nonempty and contains ξ r e f \xi_{\mathrm{ref}} ξ ref . At ξ = ξ − \xi=\xi^{-} ξ = ξ − , w k + 1 = 0 w_{k+1}=0 w k + 1 = 0 and the configuration is the k k k -point Gauss quadrature rule of the reference: the 2 k 2k 2 k outer rays sit at ± x \pm\sqrt{x} ± x for the zeros x x x of F k F_k F k , with the Christoffel numbers as weights.
Proof. Step 1 (the admissible set is an interval with lower end ξ ∗ > ξ 0 ′ \xi^{*}>\xi'_0 ξ ∗ > ξ 0 ′ ). Let ξ r e f \xi_{\mathrm{ref}} ξ ref be such that ν ξ r e f ′ \nu'_{\xi_{\mathrm{ref}}} ν ξ ref ′ is the x x x -reweighting of the reference law of s 2 s^2 s 2 (it exists by Corollary A.27, since that reweighting is a k k k -atom measure with moments m 0 ′ , … , m 2 k − 2 ′ m'_0,\ldots,m'_{2k-2} m 0 ′ , … , m 2 k − 2 ′ ). The reference has w k + 1 > 0 w_{k+1}>0 w k + 1 > 0 , so g ( ξ r e f ) < 1 / m 1 g(\xi_{\mathrm{ref}})<1/m_1 g ( ξ ref ) < 1/ m 1 . By Proposition A.36 and the intermediate value theorem there is a unique ξ ∗ ∈ ( ξ 0 ′ , ξ r e f ) \xi^{*}\in(\xi'_0,\xi_{\mathrm{ref}}) ξ ∗ ∈ ( ξ 0 ′ , ξ ref ) with g ( ξ ∗ ) = 1 / m 1 g(\xi^{*})=1/m_1 g ( ξ ∗ ) = 1/ m 1 , and { ξ > ξ 0 ′ : w k + 1 > 0 } = ( ξ ∗ , ∞ ) \{\xi>\xi'_0:w_{k+1}>0\}=(\xi^{*},\infty) { ξ > ξ 0 ′ : w k + 1 > 0 } = ( ξ ∗ , ∞ ) . On this set all t i ′ > 0 t'_i>0 t i ′ > 0 .
Step 2 ( ξ ∗ \xi^{*} ξ ∗ is the Gauss rule). The reference law of s 2 s^2 s 2 is supported on k + 1 k+1 k + 1 points ( 0 (0 ( 0 and t ~ 1 , … , t ~ k ) \tilde{t}_1,\ldots,\tilde{t}_k) t ~ 1 , … , t ~ k ) , so its k × k k\times k k × k Hankel matrix is positive definite and F k F_k F k is well defined from m 0 , … , m 2 k − 1 m_0,\ldots,m_{2k-1} m 0 , … , m 2 k − 1 . The k k k -point Gauss rule γ = ∑ i = 1 k λ i δ x i \gamma=\sum_{i=1}^{k}\lambda_i\delta_{x_i} γ = ∑ i = 1 k λ i δ x i has nodes at the zeros of F k F_k F k , positive Christoffel numbers λ i \lambda_i λ i , and is exact for polynomials of degree ≤ 2 k − 1 \le2k-1 ≤ 2 k − 1 [20 , 49 ] . Its nodes lie in the interior of the convex hull of the reference support, ( 0 , t ~ 1 ) ⊂ ( 0 , T ) (0,\tilde{t}_1)\subset(0,T) ( 0 , t ~ 1 ) ⊂ ( 0 , T ) . Exactness gives ∑ i λ i x i = m 1 \sum_i\lambda_i x_i=m_1 ∑ i λ i x i = m 1 , so γ ′ = ∑ i λ i x i m 1 δ x i \gamma'=\sum_i\frac{\lambda_i x_i}{m_1}\delta_{x_i} γ ′ = ∑ i m 1 λ i x i δ x i is a k k k -atom probability measure with moments m 0 ′ , … , m 2 k − 2 ′ m'_0,\ldots,m'_{2k-2} m 0 ′ , … , m 2 k − 2 ′ . By Corollary A.27, γ ′ = ν ξ ^ ′ \gamma'=\nu'_{\hat{\xi}} γ ′ = ν ξ ^ ′ for some ξ ^ \hat{\xi} ξ ^ , with t i ′ ( ξ ^ ) = x i > 0 t'_i(\hat{\xi})=x_i>0 t i ′ ( ξ ^ ) = x i > 0 and ( v i ′ ( ξ ^ ) ) 1 2 = λ i x i / m 1 (v'_i(\hat{\xi}))_1^2=\lambda_i x_i/m_1 ( v i ′ ( ξ ^ ) ) 1 2 = λ i x i / m 1 . Then
w k + 1 ( ξ ^ ) = 1 − m 1 ∑ i λ i x i / m 1 x i = 1 − ∑ i λ i = 0. w_{k+1}(\hat{\xi})=1-m_1\sum_i\frac{\lambda_i x_i/m_1}{x_i}=1-\sum_i\lambda_i=0. w k + 1 ( ξ ^ ) = 1 − m 1 i ∑ x i λ i x i / m 1 = 1 − i ∑ λ i = 0.
By uniqueness in Step 1, ξ ^ = ξ ∗ \hat{\xi}=\xi^{*} ξ ^ = ξ ∗ . At this point μ ξ ∗ = γ \mu_{\xi^{*}}=\gamma μ ξ ∗ = γ , which is the Gauss rule claimed.
Step 3 (closed form). By Proposition A.29 (the trace identity) applied to J ′ J' J ′ , ∑ i t i ′ ( ξ ) = ∑ j = 0 k − 2 a j ′ + ξ \sum_i t'_i(\xi)=\sum_{j=0}^{k-2}a'_j+\xi ∑ i t i ′ ( ξ ) = ∑ j = 0 k − 2 a j ′ + ξ . At ξ ∗ \xi^{*} ξ ∗ the left side is ∑ i x i \sum_i x_i ∑ i x i , the sum of the zeros of F k F_k F k , which is minus its subleading coefficient. From the recurrence of Proposition A.21 for the reference, the subleading coefficient γ k \gamma_k γ k of F k F_k F k satisfies γ j + 1 = γ j − α j \gamma_{j+1}=\gamma_j-\alpha_j γ j + 1 = γ j − α j with γ 0 = 0 \gamma_0=0 γ 0 = 0 (as in the proof of Proposition A.22), so ∑ i x i = − γ k = ∑ j = 0 k − 1 α j \sum_i x_i=-\gamma_k=\sum_{j=0}^{k-1}\alpha_j ∑ i x i = − γ k = ∑ j = 0 k − 1 α j . Hence ξ ∗ = ∑ j = 0 k − 1 α j − ∑ j = 0 k − 2 a j ′ = ξ − \xi^{*}=\sum_{j=0}^{k-1}\alpha_j-\sum_{j=0}^{k-2}a'_j=\xi^{-} ξ ∗ = ∑ j = 0 k − 1 α j − ∑ j = 0 k − 2 a j ′ = ξ − .
Step 4 (upper endpoint). The middle ray adds no constraint on t 1 ′ t'_1 t 1 ′ , so the condition t 1 ′ ≤ T t'_1\le T t 1 ′ ≤ T is ξ ≤ ξ + \xi\le\xi^{+} ξ ≤ ξ + exactly as in Theorem A.31, applied to the primed construction. The interlacing step there needs the zeros of f k − 1 ′ f'_{k-1} f k − 1 ′ to lie in ( 0 , T ) (0,T) ( 0 , T ) ; this holds because ν ξ r e f ′ \nu'_{\xi_{\mathrm{ref}}} ν ξ ref ′ is supported on { t ~ 1 , … , t ~ k } ⊂ ( 0 , T ] \{\tilde{t}_1,\ldots,\tilde{t}_k\}\subset(0,T] { t ~ 1 , … , t ~ k } ⊂ ( 0 , T ] .
Step 5 (nonempty). The reference is admissible, so ξ r e f ∈ ( ξ − , ξ + ] \xi_{\mathrm{ref}}\in(\xi^{-},\xi^{+}] ξ ref ∈ ( ξ − , ξ + ] .
Corollary A.38 (Uniqueness of construction, K K K odd). Let K = 2 k + 1 K=2k+1 K = 2 k + 1 , and let Θ \Theta Θ be an admissible configuration with K K K communities and radial law R R R whose moments m 0 , … , m 2 k − 1 m_0,\ldots,m_{2k-1} m 0 , … , m 2 k − 1 match those of the reference. Then Θ \Theta Θ is the configuration of Definition A.32 for some ξ ∈ ( ξ − , ξ + ] \xi\in(\xi^{-},\xi^{+}] ξ ∈ ( ξ − , ξ + ] .
Proof. Write μ Θ = w k + 1 δ 0 + ∑ i = 1 k 2 w i δ t i \mu_{\Theta}=w_{k+1}\delta_0+\sum_{i=1}^{k}2w_i\delta_{t_i} μ Θ = w k + 1 δ 0 + ∑ i = 1 k 2 w i δ t i with t 1 > ⋯ > t k > 0 t_1>\cdots>t_k>0 t 1 > ⋯ > t k > 0 . The atom at 0 0 0 does not contribute to m d m_d m d for d ≥ 1 d\ge1 d ≥ 1 , so m 1 = ∑ i 2 w i t i > 0 m_1=\sum_i2w_it_i>0 m 1 = ∑ i 2 w i t i > 0 and
ν Θ ′ : = ∑ i = 1 k 2 w i t i m 1 δ t i \nu'_{\Theta}:=\sum_{i=1}^{k}\frac{2w_it_i}{m_1}\delta_{t_i} ν Θ ′ := i = 1 ∑ k m 1 2 w i t i δ t i
is a probability measure with exactly k k k atoms and moments m d + 1 / m 1 = m d ′ m_{d+1}/m_1=m'_d m d + 1 / m 1 = m d ′ for 0 ≤ d ≤ 2 k − 2 0\le d\le2k-2 0 ≤ d ≤ 2 k − 2 . By Corollary A.27 applied to the primed data, ν Θ ′ = ν ξ ′ \nu'_{\Theta}=\nu'_{\xi} ν Θ ′ = ν ξ ′ for ξ = a ~ k − 1 ′ ( ν Θ ′ ) \xi=\tilde{a}'_{k-1}(\nu'_{\Theta}) ξ = a ~ k − 1 ′ ( ν Θ ′ ) . So t i = t i ′ t_i=t'_i t i = t i ′ and 2 w i t i / m 1 = ( v i ′ ) 1 2 2w_it_i/m_1=(v'_i)^2_1 2 w i t i / m 1 = ( v i ′ ) 1 2 , i.e. w i = m 1 2 t i ( v i ′ ) 1 2 w_i=\frac{m_1}{2t_i}(v'_i)^2_1 w i = 2 t i m 1 ( v i ′ ) 1 2 , the outer weights of Definition A.32. The middle weight is 1 − ∑ i ≠ k + 1 w i 1-\sum_{i\ne k+1}w_i 1 − ∑ i = k + 1 w i in both. Finally, Θ \Theta Θ is admissible, so ξ ∈ ( ξ − , ξ + ] \xi\in(\xi^{-},\xi^{+}] ξ ∈ ( ξ − , ξ + ] by Theorem A.37.
Example A.39 (K = 3 K = 3 K = 3 ). Here k = 1 k = 1 k = 1 , J ′ = [ ξ ] J' = [\xi] J ′ = [ ξ ] , t 1 ′ = ξ t'_1 = \xi t 1 ′ = ξ , w 1 = w 3 = m 1 / ( 2 ξ ) w_1 = w_3 = m_1/(2\xi) w 1 = w 3 = m 1 / ( 2 ξ ) and w 2 = 1 − m 1 / ξ w_2 = 1 - m_1/\xi w 2 = 1 − m 1 / ξ . The formula gives ξ − = α 0 = m 1 \xi^- = \alpha_0 = m_1 ξ − = α 0 = m 1 , the one-point Gauss rule (node m 1 m_1 m 1 , weight 1), and w 2 > 0 w_2 > 0 w 2 > 0 if and only if ξ > m 1 \xi> m_1 ξ > m 1 . The fiber is ξ ∈ ( m 1 , T ] \xi\in(m_1, T] ξ ∈ ( m 1 , T ] , and the free moment is m 2 = m 1 ξ m_2 = m_1\xi m 2 = m 1 ξ , strictly increasing as Corollary A.34 predicts.
Remark (Both parities). For every K ≥ 2 K \ge2 K ≥ 2 the construction produces a one-parameter family sharing R R R with m 0 , … , m K − 2 m_0,\ldots,m_{K-2} m 0 , … , m K − 2 matched and m K − 1 m_{K-1} m K − 1 strictly increasing in ξ \xi ξ (Corollaries A.26 and A.34 ). For K K K even both endpoints are Gauss–Radau rules (nodes pinned at 0 and at T T T ). For K K K odd the upper endpoint is Gauss–Radau at T T T , and the lower endpoint is the Gauss rule, where the configuration collapses to K − 1 K - 1 K − 1 communities because the middle ray loses its mass.
Motif Densities Along the Fiber
Fix K ≥ 2 K \ge2 K ≥ 2 and an admissible reference configuration Θ ~ \widetilde{\Theta} Θ with radial law R R R . Write Θ ξ \Theta_\xi Θ ξ for the configuration produced by Definition A.19 (K K K even) or Definition A.32 (K K K odd), and
Φ ~ ( Θ ~ ) : = { Θ ξ : ξ ∈ ( ξ − , ξ + ] } \widetilde{\Phi}(\widetilde{\Theta}) := \{\Theta_\xi: \xi\in(\xi^-,\xi^+]\} Φ ( Θ ) := { Θ ξ : ξ ∈ ( ξ − , ξ + ]}
for the fiber through Θ ~ \widetilde{\Theta} Θ , with ξ ± \xi^\pm ξ ± from Theorem A.31 or Theorem A.37 . Every member of Φ ~ ( Θ ~ ) \widetilde{\Phi}(\widetilde{\Theta}) Φ ( Θ ) is admissible, has K K K communities (distinct slopes, positive weights), and has radial law R R R . By Corollaries A.27 and A.38 , Φ ~ ( Θ ~ ) \widetilde{\Phi}(\widetilde{\Theta}) Φ ( Θ ) is exactly the set of admissible K K K -community configurations with radial law R R R whose slope moments m 0 , … , m K − 2 m_0,\ldots,m_{K-2} m 0 , … , m K − 2 agree with those of Θ ~ \widetilde{\Theta} Θ .
By Corollaries A.26 and A.34 , for all ξ 1 < ξ 2 \xi_1 < \xi_2 ξ 1 < ξ 2 in ( ξ − , ξ + ] (\xi^-,\xi^+] ( ξ − , ξ + ] ,
Θ ξ 1 ∼ K − 2 Θ ξ 2 , Θ ξ 1 ≁ K − 1 Θ ξ 2 , m K − 1 ( Θ ξ 1 ) < m K − 1 ( Θ ξ 2 ) , (2) \Theta_{\xi_1} \sim_{K-2} \Theta_{\xi_2}, \qquad\Theta_{\xi_1} \mathrel{\not\sim}_{K-1} \Theta_{\xi_2}, \qquad m_{K-1}(\Theta_{\xi_1}) < m_{K-1}(\Theta_{\xi_2}), \tag*{(2)} Θ ξ 1 ∼ K − 2 Θ ξ 2 , Θ ξ 1 ∼ K − 1 Θ ξ 2 , m K − 1 ( Θ ξ 1 ) < m K − 1 ( Θ ξ 2 ) , (2)
and m K − 1 ( Θ ξ ) = σ K ξ + c K m_{K-1}(\Theta_\xi) = \sigma_K \xi+ c_K m K − 1 ( Θ ξ ) = σ K ξ + c K is affine in ξ \xi ξ with slope
σ K = ∣ f k − 1 ∣ 2 ( K = 2 k ) , σ K = m 1 ∣ f k − 1 ′ ∣ 2 ( K = 2 k + 1 ) . \sigma_K = |f_{k-1}|^2 \ (K = 2k), \qquad\sigma_K = m_1|f'_{k-1}|^2 \ (K = 2k + 1). σ K = ∣ f k − 1 ∣ 2 ( K = 2 k ) , σ K = m 1 ∣ f k − 1 ′ ∣ 2 ( K = 2 k + 1 ) .
So ord ( Θ ξ 1 , Θ ξ 2 ) = K − 2 \operatorname{ord}(\Theta_{\xi_1}, \Theta_{\xi_2}) = K - 2 ord ( Θ ξ 1 , Θ ξ 2 ) = K − 2 for every pair of distinct fiber points. Everything below follows from (2) and Section A.1.
Matched motifs
Theorem A.40 (Matched motifs). Let Θ , Θ ′ ∈ Φ ~ ( Θ ~ ) \Theta, \Theta' \in\widetilde{\Phi}(\widetilde{\Theta}) Θ , Θ ′ ∈ Φ ( Θ ) . Then t ( F ; Θ ) = t ( F ; Θ ′ ) t(F;\Theta) = t(F;\Theta') t ( F ; Θ ) = t ( F ; Θ ′ ) for every graph F F F with h ( F ) ≤ K − 2 h(F) \le K - 2 h ( F ) ≤ K − 2 . In particular this holds for
every graph on at most 2 K − 2 2K - 2 2 K − 2 vertices, i.e. Cen 2 K − 2 \operatorname{Cen}_{2K-2} Cen 2 K − 2 is constant on Φ ~ ( Θ ~ ) \widetilde{\Phi}(\widetilde{\Theta}) Φ ( Θ ) ;
every graph of maximum degree at most 2 K − 3 2K - 3 2 K − 3 , regardless of its number of vertices;
every forest (these do not depend on the slopes at all).
The same holds for induced (graphlet) densities of order at most 2 K − 2 2K - 2 2 K − 2 .
Proof. By (2), Θ ∼ K − 2 Θ ′ \Theta\sim_{K-2} \Theta' Θ ∼ K − 2 Θ ′ , and both share R R R . Theorem A.14 (1) gives the main claim. Item 1 is Corollary A.18 (1) with j = K − 2 j = K - 2 j = K − 2 . Item 2 is Proposition A.15 (1): Δ ( F ) ≤ 2 K − 3 \Delta(F) \le2K - 3 Δ ( F ) ≤ 2 K − 3 gives h ( F ) ≤ K − 2 h(F) \le K - 2 h ( F ) ≤ K − 2 . Item 3 is h ( F ) = 0 h(F) = 0 h ( F ) = 0 . The induced statement follows from the Möbius remark in Section A.1.2. □
Remark. Item 2 says the obstruction is controlled by degree, not size. For instance, for K = 4 K = 4 K = 4 every cycle, every cubic graph and every graph of maximum degree 5 has constant density along the fiber, however large.
Corollary A.41 (No fixed census order suffices). For every m ≥ 2 m \ge2 m ≥ 2 there exist K K K and a fiber Φ ( Θ ~ ) \Phi(\widetilde{\Theta}) Φ ( Θ ) containing more than one configuration (indeed a continuum) on which Cen m \operatorname{Cen}_m Cen m is constant.
Proof. Take K K K with 2 K − 2 ≥ m 2K-2 \ge m 2 K − 2 ≥ m and any admissible reference with K K K communities (for example equal weights, slopes ± \pm ± equally spaced in ( 0 , T ) (0,\sqrt{T}) ( 0 , T ) , and R R R uniform on ( 0 , C ) (0,C) ( 0 , C ) with C < 1 C<1 C < 1 ). Its fiber is a nondegenerate interval by Theorem A.31 or A.37, and distinct ξ \xi ξ give distinct configurations (Proposition A.29 ). Apply Theorem A.40 .
Smallest breaker motif
Theorem A.42 (Breaker motifs). Let ξ 1 < ξ 2 \xi_1 < \xi_2 ξ 1 < ξ 2 in ( ξ − , ξ + ] (\xi_-,\xi_+] ( ξ − , ξ + ] .
(Monotone separation.) For every F F F with h ( F ) = K − 1 h(F)=K-1 h ( F ) = K − 1 , t ( F ; Θ ξ 1 ) < t ( F ; Θ ξ 2 ) t(F;\Theta_{\xi_1})<t(F;\Theta_{\xi_2}) t ( F ; Θ ξ 1 ) < t ( F ; Θ ξ 2 ) . So each such density is strictly increasing along the fiber, and in particular injective on it.
(Minimal order.) No graph on at most 2 K − 2 2K-2 2 K − 2 vertices separates Θ ξ 1 \Theta_{\xi_1} Θ ξ 1 from Θ ξ 2 \Theta_{\xi_2} Θ ξ 2 . A graph F F F on exactly 2 K − 1 2K-1 2 K − 1 vertices separates them if and only if F F F has a vertex v v v adjacent to all others such that every connected component of F [ N ( v ) ] F[N(v)] F [ N ( v )] *has an even number of vertices. Hence Cen 2 K − 1 ( Θ ξ 1 ) ≠ Cen 2 K − 1 ( Θ ξ 2 ) \operatorname{Cen}_{2K-1}(\Theta_{\xi_1}) \ne\operatorname{Cen}_{2K-1}(\Theta_{\xi_2}) Cen 2 K − 1 ( Θ ξ 1 ) = Cen 2 K − 1 ( Θ ξ 2 ) .
(Smallest breaker.) Among separating graphs on 2 K − 1 2K-1 2 K − 1 vertices, the friendship graph F K − 1 F_{K-1} F K − 1 is the unique one, up to isomorphism, with the fewest edges (3 ( K − 1 ) 3(K-1) 3 ( K − 1 ) ).
(Signal.) For K ≥ 3 K \ge3 K ≥ 3 , t ( F K − 1 ; Θ ξ ) t(F_{K-1};\Theta_\xi) t ( F K − 1 ; Θ ξ ) is affine in ξ \xi ξ :
t ( F K − 1 ; Θ ξ 2 ) − t ( F K − 1 ; Θ ξ 1 ) = ρ 2 K − 2 ρ 2 2 K − 2 m 1 2 K − 2 σ K ( ξ 2 − ξ 1 ) . t(F_{K-1};\Theta_{\xi_2})-t(F_{K-1};\Theta_{\xi_1})=\rho_{2K-2}\rho_2^{2K-2}m_1^{2K-2}\sigma_K(\xi_2-\xi_1). t ( F K − 1 ; Θ ξ 2 ) − t ( F K − 1 ; Θ ξ 1 ) = ρ 2 K − 2 ρ 2 2 K − 2 m 1 2 K − 2 σ K ( ξ 2 − ξ 1 ) . Proof. (1) By (2), apply Theorem A.14 (2) with j = K − 1 j=K-1 j = K − 1 .
(2) The first claim is Theorem A.40 (1). A graph on 2 K − 1 2K-1 2 K − 1 vertices has h ( F ) ≤ K − 1 h(F)\le K-1 h ( F ) ≤ K − 1 (Proposition A.15 (2)). If h ( F ) ≤ K − 2 h(F)\le K-2 h ( F ) ≤ K − 2 it does not separate (Theorem A.40 ); if h ( F ) = K − 1 h(F)=K-1 h ( F ) = K − 1 it does, by (1). Proposition A.17 with j = K − 1 j=K-1 j = K − 1 identifies the graphs with h ( F ) = K − 1 h(F)=K-1 h ( F ) = K − 1 . F K − 1 F_{K-1} F K − 1 is one of them (Example A.16 ), so the census of order 2 K − 1 2K-1 2 K − 1 differs.
(3) Let F F F separate, with v v v as in (2), and write j = K − 1 j=K-1 j = K − 1 . F F F has 2 j 2j 2 j edges at v v v . F [ N ( v ) ] F[N(v)] F [ N ( v )] has 2 j 2j 2 j vertices, and since its components have even order it has no isolated vertices, so its degrees sum to at least 2 j 2j 2 j and it has at least j j j edges. Hence ∣ E ( F ) ∣ ≥ 3 j |E(F)|\ge3j ∣ E ( F ) ∣ ≥ 3 j . Equality forces every vertex of F [ N ( v ) ] F[N(v)] F [ N ( v )] to have degree exactly 1 1 1 , i.e. F [ N ( v ) ] F[N(v)] F [ N ( v )] is a perfect matching, and then F ≅ F j F\cong F_j F ≅ F j .
(4) By Example A.16 ,
t ( F K − 1 ; Θ ) = ρ 2 K − 2 ρ 2 2 K − 2 ∑ i = 0 K − 1 ( K − 1 i ) m 1 2 i m i . t(F_{K-1};\Theta)=\rho_{2K-2}\rho_2^{2K-2}\sum_{i=0}^{K-1}\binom{K-1}{i}m_1^{2i}m_i. t ( F K − 1 ; Θ ) = ρ 2 K − 2 ρ 2 2 K − 2 i = 0 ∑ K − 1 ( i K − 1 ) m 1 2 i m i . For K ≥ 3 K\ge3 K ≥ 3 , m 1 m_1 m 1 is among the matched moments, so every term with i ≤ K − 2 i\le K-2 i ≤ K − 2 is constant on the fiber, and the i = K − 1 i=K-1 i = K − 1 term is ρ 2 K − 2 ρ 2 2 K − 2 m 1 2 K − 2 m K − 1 \rho_{2K-2}\rho_2^{2K-2}m_1^{2K-2}m_{K-1} ρ 2 K − 2 ρ 2 2 K − 2 m 1 2 K − 2 m K − 1 with m K − 1 = σ K ξ + c K m_{K-1}=\sigma_K\xi+c_K m K − 1 = σ K ξ + c K .
Remark (K = 2 K=2 K = 2 ). For K = 2 K=2 K = 2 the only matched moment is m 0 m_0 m 0 , and m 1 = ξ m_1=\xi m 1 = ξ itself varies. Items (1)–(3) still hold: the edge density (2 vertices) is constant and the triangle F 1 F_1 F 1 is the unique separator on 3 vertices. But t ( F 1 ; Θ ξ ) = ρ 2 2 ( 1 + ξ 3 ) t(F_1;\Theta_\xi)=\rho_2^2(1+\xi^3) t ( F 1 ; Θ ξ ) = ρ 2 2 ( 1 + ξ 3 ) is cubic rather than affine in ξ \xi ξ .
Remark (Size of the separating signal). Every factor in item (4) is small. m 1 = E [ s 2 ] ≤ t 1 ≤ T ≤ 1 m_1=\mathbb{E}[s^2]\le t_1\le T\le1 m 1 = E [ s 2 ] ≤ t 1 ≤ T ≤ 1 , and ρ d ≤ C d \rho_d\le C^d ρ d ≤ C d with C 2 ≤ 1 / 2 C^2\le1/2 C 2 ≤ 1/2 whenever T = 1 T=1 T = 1 (and C 2 < 1 C^2<1 C 2 < 1 in general). So the leading factor ρ 2 K − 2 ρ 2 2 K − 2 m 1 2 K − 2 \rho_{2K-2}\rho_2^{2K-2}m_1^{2K-2} ρ 2 K − 2 ρ 2 2 K − 2 m 1 2 K − 2 decays geometrically in K K K . The density difference that the census must resolve is therefore both of high order (2 K − 1 2K-1 2 K − 1 vertices) and geometrically small, which is the source of the census-detection cost discussed in § 5 .
Remark. Theorem A.42 says nothing about graphs with h ( F ) ≥ K h(F)\ge K h ( F ) ≥ K . Their densities involve m K , m K + 1 , … m_K,m_{K+1},\ldots m K , m K + 1 , … , which also move along the fiber, but not necessarily monotonically. Whether every such F F F separates every pair of fiber points is left open. It is not needed: F K − 1 F_{K-1} F K − 1 alone already separates every pair.
Additional proofs
Proof of Theorem 5.1. By Theorem A.11, each term is ∏ v m deg S ( v ) / 2 \prod_v m_{\deg_S(v)/2} ∏ v m d e g S ( v ) /2 . Suppose it contains m j m_j m j , so some v v v has deg S ( v ) = 2 j \deg_S(v)=2j deg S ( v ) = 2 j . Then v v v has 2 j 2j 2 j distinct S S S -neighbours u u u , each with deg S ( u ) ≥ 1 \deg_S(u)\ge1 deg S ( u ) ≥ 1 and even, so deg S ( u ) ≥ 2 \deg_S(u)\ge2 deg S ( u ) ≥ 2 . Since s 2 ∈ [ 0 , T ] ⊂ [ 0 , 1 ] s^2 \in[0,T] \subset[0,1] s 2 ∈ [ 0 , T ] ⊂ [ 0 , 1 ] , we have m r = E [ s 2 r ] ≤ E [ s 2 ] = m 1 m_r=\mathbb{E}[s^{2r}]\le\mathbb{E}[s^2]=m_1 m r = E [ s 2 r ] ≤ E [ s 2 ] = m 1 for r ≥ 1 r\ge1 r ≥ 1 , and m r ≤ m 0 = 1 m_r\le m_0=1 m r ≤ m 0 = 1 for all r r r . Bound the factor of v v v by m j m_j m j , those of its 2 j 2j 2 j neighbours by m 1 m_1 m 1 , and the rest by 1 1 1 . For F j F_j F j , the union of all j j j triangles gives exactly m j m 1 2 j m_jm_1^{2j} m j m 1 2 j (Theorem A.16).
Proof of Theorem 3.5. ( ⇐ ) (\Leftarrow) ( ⇐ ) This is Theorem A.40 (1). ( ⇒ ) (\Rightarrow) ( ⇒ ) Suppose Θ \Theta Θ shares R R R , has K K K communities, is admissible and has the same census of order 2 K − 2 2K-2 2 K − 2 as Θ ~ \widetilde{\Theta} Θ , but Θ ∉ Φ ( Θ ~ ) \Theta\notin\Phi(\widetilde{\Theta}) Θ ∈ / Φ ( Θ ) . By the characterization of Φ ( Θ ~ ) \Phi(\widetilde{\Theta}) Φ ( Θ ) in Section A.4, m ~ d ( Θ ) ≠ m ~ d ( Θ ~ ) \widetilde{m}_d(\Theta)\ne\widetilde{m}_d(\widetilde{\Theta}) m d ( Θ ) = m d ( Θ ) for some d ≤ K − 2 d\le K-2 d ≤ K − 2 . Let j j j be the smallest such d d d ; j ≥ 1 j\ge1 j ≥ 1 since m 0 = 1 m_0=1 m 0 = 1 . Then Θ ∼ j o Θ ~ \Theta\mathrel{\sim^o_j}\widetilde{\Theta} Θ ∼ j o Θ and their m ~ j \widetilde{m}_j m j differ. The friendship graph F j F_j F j has h ( F j ) = j h(F_j)=j h ( F j ) = j and 2 j + 1 ≤ 2 K − 3 2j+1\le2K-3 2 j + 1 ≤ 2 K − 3 vertices, so Theorem A.14 (2) gives t ( F j ; Θ ) ≠ t ( F j ; Θ ~ ) t(F_j;\Theta)\ne t(F_j;\widetilde{\Theta}) t ( F j ; Θ ) = t ( F j ; Θ ) , a contradiction.
Proof of Theorem 3.3. (1) Trees. A tree T T T is acyclic, so its cycle space is trivial and E ( T ) = { ∅ } \mathcal{E}(T)=\{\varnothing\} E ( T ) = { ∅ } . By Theorem A.11 , τ ( T ; π ) = 1 \tau(T;\pi)=1 τ ( T ; π ) = 1 , so by Theorem A.9, t ( T ; Θ ) = ∏ v ρ deg T v t(T;\Theta)=\prod_v \rho_{\deg_T v} t ( T ; Θ ) = ∏ v ρ d e g T v , which depends on R R R only. (2) Refinement. On the graphon with points z = ( c , x ) z=(c,x) z = ( c , x ) and kernel W ( z , z ′ ) = x x ′ ( 1 + s c s c ′ ) W(z,z')=xx'(1+s_cs_{c'}) W ( z , z ′ ) = x x ′ ( 1 + s c s c ′ ) , the round-0 color is constant, and the round-( t + 1 ) (t+1) ( t + 1 ) color of z z z is the measure A ↦ ∫ 1 { col t ( z ′ ) ∈ A } W ( z , z ′ ) d P ( z ′ ) A\mapsto\int1\{\operatorname{col}_t(z')\in A\}W(z,z')\,dP(z') A ↦ ∫ 1 { col t ( z ′ ) ∈ A } W ( z , z ′ ) d P ( z ′ ) ([24 , 10 ] ). Suppose col t ( c , x ) = f t ( x ) \operatorname{col}_t(c,x)=f_t(x) col t ( c , x ) = f t ( x ) . The community of z ′ z' z ′ is independent of its radius and E [ s ] = 0 \mathbb{E}[s]=0 E [ s ] = 0 , so this measure is x ( 1 + s c E [ s ] ) ∫ 1 { f t ( x ′ ) ∈ A } x ′ d R ( x ′ ) = x ∫ 1 { f t ( x ′ ) ∈ A } x ′ d R ( x ′ ) x(1+s_c\mathbb{E}[s])\int1\{f_t(x')\in A\}x'\,dR(x')=x\int1\{f_t(x')\in A\}x'\,dR(x') x ( 1 + s c E [ s ]) ∫ 1 { f t ( x ′ ) ∈ A } x ′ d R ( x ′ ) = x ∫ 1 { f t ( x ′ ) ∈ A } x ′ d R ( x ′ ) , which depends on x x x only. By induction every color is a function of the radius, so configurations sharing R R R have the same distribution of colors. (3) Networks. The model is a graphon on the standard probability space Ω = [ K ] × ( 0 , C ) \Omega=[K]\times(0,C) Ω = [ K ] × ( 0 , C ) with law π Θ ⊗ R \pi_\Theta\otimes R π Θ ⊗ R . Moving it to [ 0 , 1 ] [0,1] [ 0 , 1 ] by a measure-preserving map changes neither tree densities nor the distribution of colors ([32 ] ). Böker et al. [10 ] consider networks with Lipschitz updates h ( t ) ( x ) = φ t ( ∫ W ( x , y ) h ( t − 1 ) ( y ) d y ) h^{(t)}(x)=\varphi_t(\int W(x,y)h^{(t-1)}(y)\,dy) h ( t ) ( x ) = φ t ( ∫ W ( x , y ) h ( t − 1 ) ( y ) d y ) , the graphon form of sum aggregation normalized by the number of nodes, readout ψ ( ∫ h ( L ) ) \psi(\int h^{(L)}) ψ ( ∫ h ( L ) ) , and no node features. For this class, the output is a function of the distribution of colors, and two graphons get equal outputs from every network iff their tree densities agree ([10 Theorems 12 and 28] ). Apply (1) and (2). The argument of (2) also covers aggregation normalized by degree, since the degree x ρ 1 x\rho_1 x ρ 1 is a function of the color; that class is outside the cited theorem.
Census Route: Details
Homomorphism counts are unbiased for the separation. For a graph H H H on m m m vertices, grouping maps by which vertices coincide gives E [ hom ( H , G ) / n m ] = ∑ P ( n ∣ P ∣ ) / n m t ( H / P ) \mathbb{E}[\operatorname{hom}(H,G)/n^m]=\sum_P \binom{n}{|P|}/n^m\,t(H/P) E [ hom ( H , G ) / n m ] = ∑ P ( ∣ P ∣ n ) / n m t ( H / P ) over partitions P P P of V ( H ) V(H) V ( H ) . Every proper quotient H / P H/P H / P has at most m − 1 m-1 m − 1 vertices; for H = F K − 1 H=F_{K-1} H = F K − 1 (m = 2 K − 1 m=2K-1 m = 2 K − 1 ) its density is therefore constant along the fiber (Theorem A.40 ). In the difference between two fiber configurations every degenerate term cancels, leaving ( n m ) / n m ( t X ( H ) − t Y ( H ) ) \binom{n}{m}/n^m\bigl(t_X(H)-t_Y(H)\bigr) ( m n ) / n m ( t X ( H ) − t Y ( H ) ) , and the known factor ( n m ) / n m = 1 − O ( m 2 / n ) \binom{n}{m}/n^m=1-O(m^2/n) ( m n ) / n m = 1 − O ( m 2 / n ) is divided out. The friendship ladder then reduces to per-vertex triangle counts, hom ( F r , G ) = ∑ v ( ( A 3 ) v v ) r \operatorname{hom}(F_r,G)=\sum_v((A^3)_{vv})^r hom ( F r , G ) = ∑ v (( A 3 ) v v ) r . Counts are accumulated in integer arithmetic, since the K = 4 K=4 K = 4 separation is below float32 resolution.
Estimators P2, P2′, P2″. P2 takes m 1 m_1 m 1 from λ 2 / λ 1 \lambda_2/\lambda_1 λ 2 / λ 1 , inverts t ( F 2 ) t(F_2) t ( F 2 ) and t ( F 3 ) t(F_3) t ( F 3 ) for m 2 , m 3 m_2,m_3 m 2 , m 3 , and applies Prony. P2′ estimates m 2 m_2 m 2 instead from V = t ( F 2 ) − t ( C 3 ) 2 V=t(F_2)-t(C_3)^2 V = t ( F 2 ) − t ( C 3 ) 2 , the centred second moment of per-vertex triangle counts, in which the fluctuation of the mean triangle count shared by the two densities cancels; the radial moments are estimated from star densities on the same graph, and each density is divided by its exact finite-n n n expectation. P 2 ′ ′ P2^{\prime\prime} P 2 ′′ minimizes ∑ r = 1 3 ( t ^ ( F r ) − t ( F r ; θ ) ) 2 / S D r 2 \sum_{r=1}^{3}(\hat{t}(F_r)-t(F_r;\theta))^2/\mathrm{SD}_r^2 ∑ r = 1 3 ( t ^ ( F r ) − t ( F r ; θ ) ) 2 / SD r 2 over the admissible set, with S D r \mathrm{SD}_r SD r the replicate standard deviation of the normalized density. The m 2 m_2 m 2 -dependent part of t ( F 2 ) / b a s e t(F_2)/\mathrm{base} t ( F 2 ) / base is 0.013% of the total against about 3% Monte Carlo noise, predicting S D ( m ^ 2 ) = 13.7 \mathrm{SD}(\hat{m}_2)=13.7 SD ( m ^ 2 ) = 13.7 against a measured 12.6, 234× the true m 2 m_2 m 2 . Of 12,600 replicates at the published configuration, 49.9% failed Hankel positivity and the rest returned atoms or weights out of range. A sweep of m 1 m_1 m 1 from 0.217 to 0.85 never exceeds a 2% valid rate for P2 or P2′; at m 1 = 0.85 m_1=0.85 m 1 = 0.85 , n = 32,000 n=32{,}000 n = 32 , 000 , P2′ has S N R ( m 2 ) = 126.9 \mathrm{SNR}(m_2)=126.9 SNR ( m 2 ) = 126.9 and S N R ( m 3 ) = 1.61 \mathrm{SNR}(m_3)=1.61 SNR ( m 3 ) = 1.61 and still returns 0 of 200.
P 2 ′ ′ P2^{\prime\prime} P 2 ′′ is valid, bimodal, and on the boundary. At LO, C = 0.75 C=0.75 C = 0.75 , n = 32,000 n=32{,}000 n = 32 , 000 (200 replicates) the fits fall on two point masses (Table 4 , Figure 3 ); the objective, χ 2 \chi^2 χ 2 -like on its three residuals with expectation about 3, is about 1.2 for the truth and for both corners, and all refinements converge. The reported ±23% spread is the gap between point masses, not dispersion.
Table 4. P 2 ′ ′ P2^{\prime\prime} P 2 ′′ fits at LO, C = 0.75 C=0.75 C = 0.75 , n = 32,000 n=32{,}000 n = 32 , 000 .
Figure 3. Three estimators on identical graphs at LO, C = 0.75 C=0.75 C = 0.75 , n = 32,000 n=32{,}000 n = 32 , 000 . Unconstrained P2 returns no valid slope law here and is not shown. P 2 ′ ′ P2^{\prime\prime} P 2 ′′ fits sit on the boundary of the admissible set; its ±23% replicate spread is the gap between two point masses, not dispersion.
Held-Out Scores
The held-out oracle score holds out 5% of node pairs and takes the true latent positions. For each candidate it snaps every node to the candidate’s nearest ray (by ∣ s l o p e ∣ |\mathrm{slope}| ∣ slope ∣ ), projects the position onto that ray, and scores the held-out pairs by the log-loss of the resulting inner products, clipped to [ 10 − 6 , 1 − 10 − 6 ] [10^{-6},1-10^{-6}] [ 1 0 − 6 , 1 − 1 0 − 6 ] ; the mask, outcomes and positions are shared, and only the candidate’s slopes differ. For the generating configuration the snap is the identity, so its predictions are the true edge probabilities and it must win in expectation (Gibbs’ inequality). The analytic benchmark is the population expectation of the per-pair log-loss gap, computed by Gauss–Legendre quadrature over the radial law and exact summation over slopes; it involves no graph, and n n n enters only through the conversion to a t t t -statistic. The oracle’s margin matches it at ratios 0.93–1.04 across all 36 cells.
The reconstruction (“plug-in”) score uses the same mask, sets the held-out entries of A A A to zero without rescaling (which shrinks the embedding by a factor of about 0.95 \sqrt{0.95} 0.95 , equally for both candidates), embeds, and then applies the same snap to the estimated positions: it snaps each node to the candidate’s nearest ray, projects to a radius, and scores the held-out pairs by the log-loss of the resulting inner products. Both candidates share one embedding and one mask and differ only in the snap; it compares two constrained reconstructions of one estimated point cloud and is not a likelihood ratio, so Gibbs’ inequality does not apply. It is correct at C = 0.75 C = 0.75 C = 0.75 and inverts below, always toward the same arm; the candidate’s weights never enter it. The oracle decomposition (analytic benchmark → oracle → plug-in, each adding one error source) reclassifies the 23 cells in which the plug-in score preferred the wrong configuration as construction artifacts.
Spectral Pipeline: Details
Figure 4. P1-Prony at LO, n = 32,000 n = 32{,}000 n = 32 , 000 : displaced 6.1% at C = 0.75 C = 0.75 C = 0.75 and 38.9% at C = 0.3 C = 0.3 C = 0.3 (intrinsic mean displacement, 200 replicates per cell).
Table 6. The two tilts.
Tube around the fitted ambiguity set. A tube with radius propagated from the replicate covariance of ( m ^ 1 , m ^ 2 ) (\hat{m}_1,\hat{m}_2) ( m ^ 1 , m ^ 2 ) through the level-set Jacobian covers at least 80% while staying informative in 1 of 16 groups at z = 3 z = 3 z = 3 and 0 of 16 at z = 1 , 2 z = 1, 2 z = 1 , 2 ; the one success is the cell where the point estimate is already 99.9% accurate, with bias/spread 1.47. It fails by not covering, not by becoming vacuous.
Bias scaling. Across-fiber distance at C = 0.75 C = 0.75 C = 0.75 : 4.67% → \rightarrow → 0.865% → \rightarrow → 0.161% of arc over 16× \times × in n n n (slope − 1.21 -1.21 − 1.21 ); bias/spread 6.62 → \rightarrow → 3.85 → \rightarrow → 1.47. At C = 0.3 C = 0.3 C = 0.3 the clean scaling degrades.
Published Pipelines and the Factorial
All pipelines use the same d = 2 d = 2 d = 2 ASE as P1 and cluster every row (the published recipes have no radius filter). SCORE takes η ^ 2 / η ^ 1 \hat{\eta}_2/\hat{\eta}_1 η ^ 2 / η ^ 1 with η ^ 1 \hat{\eta}_1 η ^ 1 given the Perron sign, truncates at ± log n \pm\log n ± log n , and runs one-dimensional k k k -means with K = 4 K = 4 K = 4 and 10 restarts [25 ] . Row-normalized spectral clustering runs k k k -means on unit rows [40 , 29 ] . Spherical coordinates use the authors’ transform with a Gaussian mixture, K = 4 K = 4 K = 4 , 10 initializations (Sanna Passino et al., 2022); isolated nodes give zero rows, on which the transform is undefined, so they are fitted out and assigned afterward. The shared plug-in sets each cluster’s slope to ∑ x 1 x 2 / ∑ x 1 2 \sum x_1x_2/\sum x_1^2 ∑ x 1 x 2 / ∑ x 1 2 , pairs the clusters by ∣ slope ∣ |\text{slope}| ∣ slope ∣ , and takes τ \tau τ as the mean squared slope per pair and α 1 \alpha_1 α 1 as the shallow pair’s share. Label accuracy (best permutation) at HI, C = 0.3 C = 0.3 C = 0.3 : SCORE 95.3%, row-normalized 75.4%, spherical 88.4%. SCORE’s failure at LO is bimodal: at C = 0.3 C = 0.3 C = 0.3 , 6.5% of replicates land about 81% of the arc away; at C = 0.5 C = 0.5 C = 0.5 , 34.9% land about 105% away, and 10% of fits leave the admissible set. Spherical coordinates with a GMM is also bimodal at LO in the dense control (C = 0.75 C = 0.75 C = 0.75 ): 37% of replicates land about 38% of the arc away.
Table 7. Factorial of summary pipelines (shared slope plug-in, R = 200 R = 200 R = 200 ): median total error ∣ θ ^ − θ 0 ∣ |\widehat{\theta}-\theta_0| ∣ θ − θ 0 ∣ , % of arc, by cell (mean degree), and fitted-to-true minority weight at HI (720). “Filter” is P1’s small-radius filter. The untruncated ratio matches the truncated one to within 0.3 points and is omitted.
Model-Based Fits
RayEM. Each embedded row is modeled as x ^ i = r i ( 1 , s c i ) + ε i \widehat{x}_i = r_i(1,s_{c_i})+\varepsilon_i x i = r i ( 1 , s c i ) + ε i with ε i ∼ N ( 0 , Σ ^ ( x ^ i ) / n ) \varepsilon_i \sim N(0,\widehat{\Sigma}(\widehat{x}_i)/n) ε i ∼ N ( 0 , Σ ( x i ) / n ) , where Σ ( x ) = Δ − 1 E [ ( x ⊤ Y − ( x ⊤ Y ) 2 ) Y Y ⊤ ] Δ − 1 \Sigma(x)=\Delta^{-1}\mathbb{E}[(x^\top Y-(x^\top Y)^2)YY^\top]\Delta^{-1} Σ ( x ) = Δ − 1 E [( x ⊤ Y − ( x ⊤ Y ) 2 ) Y Y ⊤ ] Δ − 1 is the ASE central-limit covariance [4 ] , Y Y Y is an independent latent position and Δ = E [ Y Y ⊤ ] \Delta=\mathbb{E}[YY^\top] Δ = E [ Y Y ⊤ ] . Replacing expectations over Y Y Y by averages over the rows, Δ ^ = n − 1 ∑ j x ^ j x ^ j ⊤ \widehat{\Delta}=n^{-1}\sum_j\widehat{x}_j\widehat{x}_j^\top Δ = n − 1 ∑ j x j x j ⊤ and E [ ( x ⊤ Y ) q Y Y ⊤ ] ≈ n − 1 ∑ j ( x ⊤ x ^ j ) q x ^ j x ^ j ⊤ \mathbb{E}[(x^\top Y)^qYY^\top]\approx n^{-1}\sum_j(x^\top\widehat{x}_j)^q\widehat{x}_j\widehat{x}_j^\top E [( x ⊤ Y ) q Y Y ⊤ ] ≈ n − 1 ∑ j ( x ⊤ x j ) q x j x j ⊤ for q = 1 , 2 q=1,2 q = 1 , 2 , which are contractions of the rows’ third- and fourth-moment tensors, so all of Σ ^ \widehat{\Sigma} Σ costs O ( n ) O(n) O ( n ) ; no ground truth, radial law or C C C is used. Slopes are ± s a , ± s b \pm s_a,\pm s_b ± s a , ± s b with reflected pairs sharing a weight. Each row’s radius is profiled out per ray in the Mahalanobis metric. The E-step assigns responsibilities from the profiled residuals and the weights; the M-step updates the weights and then s a , s b s_a,s_b s a , s b , which separate into two bounded one-dimensional problems. Seven starts are used (P1-cluster, P1-Prony, five random), and the best objective is kept. Rows are filtered as for P1, because Σ ^ \widehat{\Sigma} Σ vanishes near the origin; rows whose plug-in matrix is not positive definite get a small ridge. Validation. Under its own model (synthetic Gaussian rows at n = 32,000 n=32{,}000 n = 32 , 000 ) RayEM is unbiased to 1% of the arc. We pre-specified that it recover θ \theta θ to 10 − 6 10^{-6} 1 0 − 6 from noiseless rows. It does not: errors are 2 2 2 –3 × 10 − 3 3\times10^{-3} 3 × 1 0 − 3 , because the plug-in noise level is nonzero even for noise-free rows, so the profile objective is not stationary at the truth. The criterion holds in the zero-noise limit; we changed it to that after the first run and report both. The plug-in covariance matches the realized embedding error to 2% (ratio 0.98).
The authors’ Bayesian LSBM. We ran the Gibbs sampler of Sanna Passino and Heard [44 ] from the authors’ public code, with curves restricted to lines through the origin, on 20 graphs at each of HI (C = 0.3 C = 0.3 C = 0.3 , n = 32,000 n = 32{,}000 n = 32 , 000 ) and w min = 0.03 w_{\min} = 0.03 w m i n = 0.03 (C = 0.5 C = 0.5 C = 0.5 , n = 8000 n = 8000 n = 8000 ). Chains ran until the split-half drift of every component of θ ^ \hat{\theta} θ ^ fell below 10 − 3 10^{-3} 1 0 − 3 , with a 3-hour cap; 17 of 20 and 19 of 20 chains converged. Over all 20 chains, converged or not, along-fiber displacement was − 0.33 % -0.33\% − 0.33% and − 1.76 % -1.76\% − 1.76% (RMSE 0.81 % 0.81\% 0.81% , 2.32 % 2.32\% 2.32% ), against − 31.3 % -31.3\% − 31.3% and − 54.5 % -54.5\% − 54.5% for P1-cluster on the same graphs.
Negative Results and Pre-Registered Predictions
Richardson correction. Re-estimating on nested node subsamples (n / 2 n/2 n /2 , n / 4 n/4 n /4 ; four draws each) and extrapolating as 1 / n → 0 1/n \to0 1/ n → 0 does not remove the displacement. At the moment level, Prony on corrected moments is unstable: no valid slope law at LO (C = 0.3 C = 0.3 C = 0.3 ), and HI moves from − 9.6 % -9.6\% − 9.6% to − 22.5 % -22.5\% − 22.5% . At the estimate level, P1-cluster’s displacement at HI falls from − 31.4 % -31.4\% − 31.4% to − 16.8 % -16.8\% − 16.8% , but in the dense control cells the correction overshoots where the bias is already small: the bias there shrinks faster than 1 / n 1/n 1/ n . The overshoot is systematic (at HI, C = 0.75 C = 0.75 C = 0.75 , + 1.36 % +1.36\% + 1.36% against a baseline of − 0.24 % -0.24\% − 0.24% , many standard errors), not noise from using four subsample draws.
A single-graph detector. The drift of the estimate between n / 2 n/2 n /2 and n n n separates displaced from accurate cells with AUC 0.96, but its sign agrees with the displacement in only 67% of replicates (50% for P1-Prony), and at a threshold calibrated on the dense cells it flags every replicate of P1-cluster’s safe low-density cells. It detects low density, not displacement, and we do not recommend it.
Predictions. Before each stage we recorded predictions with pass rules. Held: estimate-level correction only partly removes P1-cluster’s displacement; RayEM removes it, with its residual error axis within 30 ∘ 30^\circ 3 0 ∘ of the tangent (8.3 ∘ 8.3^\circ 8. 3 ∘ ); RayEM with correction is within 5% at HI and LO. Failed: moment-level correction fixes Prony (no valid output at LO); the detector meets AUC ≥ 0.9 \ge0.9 ≥ 0.9 and 90% sign agreement; SCORE and row-normalized clustering both slide by more than 20% at HI (SCORE does not); untruncated ratios with k k k -means slide by more than 20% (they do not); the small-radius filter halves the slide of angle and unit-vector features (it does not). The prediction texts were fixed in code and time-stamped before the runs they concern.
Per-Cell Tables and Provenance
Every localization number is intrinsic: position and displacement are arc length along the fiber, in % of the reference arc (1.0571 in θ \theta θ , the admissible arc at C = 0.75 C = 0.75 C = 0.75 ), and every displacement is reported with its spread and RMSE. Configurations with s / a r c > 1 s/\mathrm{arc} > 1 s / arc > 1 (e.g. w min = 0.03 w_{\min} = 0.03 w m i n = 0.03 ) are admissible only for C ≤ 1 / 2 C \le1/\sqrt{2} C ≤ 1/ 2 , where the admissible fiber is longer. Tables 8 to 11 condense the per-cell results; the full tables for all 552 (estimator, configuration, C C C , n n n ) cells of each experiment are provided as ancillary files with this article, in PDF and CSV. In these tables, P1-c is P1-cluster and P1-P is P1-Prony.
Table 10. Thickened ambiguity set (a tube whose radius is propagated from the replicate covariance of ( m ^ 1 , m ^ 2 ) (\hat{m}_1,\hat{m}_2) ( m ^ 1 , m ^ 2 ) ; it uses replicate information a practitioner does not have). r 1 r_1 r 1 : tube radius at z = 1 z=1 z = 1 ; the tube at z z z has radius z r 1 z r_1 z r 1 , so z z z is the multiplier on the propagated standard deviation. Coverage and size are reported together. adm. length : admissible fiber length at that C C C , % of the reference arc (> 100 % >100\% > 100% for C < 0.75 C<0.75 C < 0.75 by construction).
Table 11. The named configurations at every ( C , n ) (C,n) ( C , n ) . disp. : intrinsic signed along-fiber bias; spread : replicate SD of the intrinsic position; both in % of the reference arc. R R R : replicates (pooled runs at n = 2000 n=2000 n = 2000 ). dist /∣ e ∣ |e| ∣ e ∣ : median distance to the fiber over the distance ∣ e ∣ = ∣ θ ^ − θ 0 ∣ |e|=|\hat{\theta}-\theta_0| ∣ e ∣ = ∣ θ ^ − θ 0 ∣ to the truth. ≤ 0.02 \le0.02 ≤ 0.02 : share of replicates within 0.02 of the fiber in θ \theta θ . Flags: bs (sign opposite to the P1-cluster branch pattern), bd (breakdown, mean degree 45), n.s. (not significant at 2 SE), boundary (configuration at the arc end).
Table per-cell.
Provenance. Eight runs on 64 CPUs and 6× RTX 6000 Ada: about 10 wall-hours for the first seven and a few more for the eighth, whose Bayesian chains were capped at 3 hours. Master seed 20260806; per-replicate seeds sha256(master∣tag) with disjoint tag prefixes across runs. Configurations loaded bit-identically from the first run. The code passes 35 unit tests, including brute-force motif enumeration for n ≤ 12 n \le12 n ≤ 12 ; the suppression identity was verified at 50 digits in three independent ways; and every cell has positive controls. Triangle and friendship-graph accumulation use integer arithmetic (the separator signal is below float32 epsilon). Python 3.12.3, numpy 1.26.4, scipy 1.11.4, pandas 2.1.4, pmpath 1.3.0, torch 2.7.0, CUDA 12.8.