In the seminal article \cite{LED16}, an integral representation of the derivatives of entropy along the heat flow of a probability measure was established under suitable moment conditions. These integral representations have found significant applications in diverse domains - notably in information theory (e.g., entropy power inequalities, monotonicity of Fisher information) and in estimation theory (through the link between entropy derivatives and the minimum mean square error, MMSE, in Gaussian channels). The representations involve multivariate polynomials $(R_n)_n$, arising from a Lie algebra framework on multilinear operators. Despite their central role, the combinatorial structure of these polynomials remains only partially understood. In this note, we prove that the number of monomials in $R_n$ coincides with the number of degree sequences with degree sum $2n$ having a non-separable graph realization, thereby resolving a conjecture from \cite{MPS24}, and drawing an interesting link between these two domains.
论文ID : 2510.14039标题 : Non-separable graphs meet Ledoux's polynomials作者 : Paul Mansanarez分类 : math.CO (组合数学)发表时间 : 2025年10月15日论文链接 : https://arxiv.org/abs/2510.14039 本文研究了Ledoux在开创性工作中建立的概率测度沿热流熵导数积分表示中涉及的多元多项式( R n ) n (R_n)_n ( R n ) n R n R_n R n 2 n 2n 2 n 8 中的一个猜想，并在这两个领域之间建立了有趣的联系。
熵导数的积分表示 ：Ledoux在文献4 中建立了概率测度沿热流的熵的n阶时间导数的积分表示：
∂ t n H ( X + 2 t N ) = ( − 2 ) n − 1 ∫ R R ~ n ( u t ( 2 ) , … , u t ( n ) ) ( x ) d x \partial^n_t H(X + \sqrt{2t}N) = (-2)^{n-1} \int_{\mathbb{R}} \tilde{R}_n(u^{(2)}_t, \ldots, u^{(n)}_t)(x) dx ∂ t n H ( X + 2 t N ) = ( − 2 ) n − 1 ∫ R R ~ n ( u t ( 2 ) , … , u t ( n ) ) ( x ) d x 多项式的重要性 ：这些表示涉及多元多项式R ~ n = X n 2 + R n \tilde{R}_n = X_n^2 + R_n R ~ n = X n 2 + R n R n R_n R n 组合结构未明 ：尽管这些多项式在理论上很重要，但其组合结构仍不完全清楚。文献8 的作者在研究这些多项式时提出了一个猜想：R n R_n R n d n s ( n ) − 1 dns(n)-1 d n s ( n ) − 1 d n s ( n ) dns(n) d n s ( n ) 2 n 2n 2 n
证明了主要猜想 ：证明了R n R_n R n d n s ( n ) − 1 dns(n)-1 d n s ( n ) − 1 建立跨领域联系 ：在Ledoux多项式理论与非可分图理论之间建立了深刻的组合联系提供构造性证明 ：通过分析多项式的递归结构和图论中的度序列性质给出了构造性证明解决开放问题 ：解决了文献8 中提出的组合猜想证明对于整数n > 2 n > 2 n > 2 R n R_n R n d n s ( n ) − 1 dns(n)-1 d n s ( n ) − 1 d n s ( n ) dns(n) d n s ( n ) 2 n 2n 2 n
R n R_n R n
R 2 = 0 R_2 = 0 R 2 = 0 R n + 1 = A n + L ( R n ) + H ( R n ) R_{n+1} = A_n + L(R_n) + H(R_n) R n + 1 = A n + L ( R n ) + H ( R n ) 其中：
A n = − ∑ k = 1 n − 1 ( n k ) X 1 + k X 1 + n − k X n A_n = -\sum_{k=1}^{n-1} \binom{n}{k} X_{1+k}X_{1+n-k}X_n A n = − ∑ k = 1 n − 1 ( k n ) X 1 + k X 1 + n − k X n L ( X 1 α 1 ⋯ X r α r ) = ∑ 1 ≤ i < j ≤ r X 1 α 1 ⋯ X i α i + 1 ⋯ X j α j + 1 ⋯ X r α r L(X^{\alpha_1}_1 \cdots X^{\alpha_r}_r) = \sum_{1 \leq i < j \leq r} X^{\alpha_1}_1 \cdots X^{\alpha_i+1}_i \cdots X^{\alpha_j+1}_j \cdots X^{\alpha_r}_r L ( X 1 α 1 ⋯ X r α r ) = ∑ 1 ≤ i < j ≤ r X 1 α 1 ⋯ X i α i + 1 ⋯ X j α j + 1 ⋯ X r α r H ( X 1 α 1 ⋯ X r α r ) = − 1 2 ∑ k = 1 r ∑ l = 1 α k − 1 ( α k l ) X 1 + l X 1 + α k − l ∏ i ≠ k X i α i H(X^{\alpha_1}_1 \cdots X^{\alpha_r}_r) = -\frac{1}{2} \sum_{k=1}^r \sum_{l=1}^{\alpha_k-1} \binom{\alpha_k}{l} X_{1+l}X_{1+\alpha_k-l} \prod_{i \neq k} X^{\alpha_i}_i H ( X 1 α 1 ⋯ X r α r ) = − 2 1 ∑ k = 1 r ∑ l = 1 α k − 1 ( l α k ) X 1 + l X 1 + α k − l ∏ i = k X i α i 定义D N S G ( n ) DNSG(n) D NSG ( n ) d = ( d 1 , … , d r ) d = (d_1, \ldots, d_r) d = ( d 1 , … , d r )
d 1 ≥ ⋯ ≥ d r ≥ 2 d_1 \geq \cdots \geq d_r \geq 2 d 1 ≥ ⋯ ≥ d r ≥ 2 ∑ k = 1 r d k = 2 n \sum_{k=1}^r d_k = 2n ∑ k = 1 r d k = 2 n d 1 ≤ d 2 + ⋯ + d r − 2 r + 4 d_1 \leq d_2 + \cdots + d_r - 2r + 4 d 1 ≤ d 2 + ⋯ + d r − 2 r + 4 通过归纳法证明I n ∗ = D N S G ( n ) I^*_n = DNSG(n) I n ∗ = D NSG ( n ) I n ∗ I^*_n I n ∗ R n R_n R n
引理2.4 ：I n + 1 ∗ = ⋃ α ∈ I n ∗ T n + 1 ( α ) I^*_{n+1} = \bigcup_{\alpha \in I^*_n} T_{n+1}(\alpha) I n + 1 ∗ = ⋃ α ∈ I n ∗ T n + 1 ( α )
这表明多项式A n + 1 A_{n+1} A n + 1 R n + 1 R_{n+1} R n + 1 L ( R n ) L(R_n) L ( R n ) H ( R n ) H(R_n) H ( R n )
递归结构分析 ：深入分析了多项式递归定义与图论度序列构造的对应关系双向包含证明 ：通过两个关键引理证明了D N S G ( n + 1 ) ⊆ ⋃ α ∈ D N S G ( n ) T n + 1 ( α ) DNSG(n+1) \subseteq \bigcup_{\alpha \in DNSG(n)} T_{n+1}(\alpha) D NSG ( n + 1 ) ⊆ ⋃ α ∈ D NSG ( n ) T n + 1 ( α ) 组合对应 ：建立了多项式操作L L L H H H 本文主要是理论工作，通过具体的小例子验证：
R 3 = − 2 X 2 3 R_3 = -2X_2^3 R 3 = − 2 X 2 3 R 4 = − 12 X 2 X 3 2 + 6 X 2 4 R_4 = -12X_2X_3^2 + 6X_2^4 R 4 = − 12 X 2 X 3 2 + 6 X 2 4 R 5 = − 20 X 2 X 4 2 − 30 X 3 2 X 4 + 120 X 2 2 X 3 2 − 24 X 2 5 R_5 = -20X_2X_4^2 - 30X_3^2X_4 + 120X_2^2X_3^2 - 24X_2^5 R 5 = − 20 X 2 X 4 2 − 30 X 3 2 X 4 + 120 X 2 2 X 3 2 − 24 X 2 5 对于n = 3 n=3 n = 3
( 3 , 3 ) (3,3) ( 3 , 3 ) ( 2 , 2 , 2 ) (2,2,2) ( 2 , 2 , 2 ) 这与R 3 R_3 R 3 d n s ( 3 ) − 1 = 2 − 1 = 1 dns(3)-1 = 2-1 = 1 d n s ( 3 ) − 1 = 2 − 1 = 1
定理1.1 ：对于整数n > 2 n > 2 n > 2 R n R_n R n d n s ( n ) − 1 dns(n)-1 d n s ( n ) − 1
通过以下两个关键引理完成了完整证明：
引理3.1 ：对于每个d ∈ D N S G ( n + 1 ) d \in DNSG(n+1) d ∈ D NSG ( n + 1 ) α ∈ D N S G ( n ) \alpha \in DNSG(n) α ∈ D NSG ( n ) d ∈ T n + 1 ( α ) d \in T_{n+1}(\alpha) d ∈ T n + 1 ( α )
引理3.2 ：对于每个α ∈ D N S G ( n ) \alpha \in DNSG(n) α ∈ D NSG ( n ) T n + 1 ( α ) ⊆ D N S G ( n + 1 ) T_{n+1}(\alpha) \subseteq DNSG(n+1) T n + 1 ( α ) ⊆ D NSG ( n + 1 )
证明不仅建立了数量上的等价性，还给出了具体的构造方法，说明了多项式中每个单项式如何对应一个特定的非可分图度序列。
Hakimi定理 （1962）：刻画了哪些度序列具有非可分图实现Rødseth-Tverberg-Sellers结果 ：给出了d n s ( 2 m ) dns(2m) d n s ( 2 m ) d n s ( 2 m ) = p ( 2 m ) − p ( 2 m − 1 ) − ∑ j = 0 m − 2 p ( j ) dns(2m) = p(2m) - p(2m-1) - \sum_{j=0}^{m-2} p(j) d n s ( 2 m ) = p ( 2 m ) − p ( 2 m − 1 ) − ∑ j = 0 m − 2 p ( j ) Ledoux的开创性工作 ：建立了熵导数的积分表示Γ-演算框架 ：多项式在马尔可夫扩散算子的迭代梯度理论中的应用MMSE猜想 ：与最小均方误差相关的信息论猜想本文成功证明了Ledoux多项式R n R_n R n 8 中的开放猜想。
跨学科联系 ：在看似无关的两个数学领域之间建立了深刻联系组合洞察 ：为理解这些重要多项式的结构提供了新的组合视角方法论贡献 ：展示了如何通过递归结构分析来建立这种对应关系进一步探索多项式系数与图论性质的关系 研究这种对应关系在信息论应用中的含义 寻找其他类似的跨领域组合对应 问题重要性 ：解决了一个具有理论意义的开放猜想证明严谨 ：提供了完整的构造性证明跨学科价值 ：在多项式理论与图论之间建立了意外的联系方法清晰 ：证明策略清晰，技术处理得当应用局限 ：主要是理论结果，实际应用价值有待进一步探索推广性 ：目前仅针对特定的Ledoux多项式，推广到其他类似结构尚不明确计算复杂性 ：未讨论相关计算的复杂性问题理论贡献 ：为组合数学和信息论的交叉研究提供了新的视角方法论价值 ：展示了通过递归结构分析建立跨领域联系的有效方法后续研究 ：可能启发更多关于多项式组合结构的研究理论研究 ：组合数学、图论、信息论的理论研究教学应用 ：作为展示数学不同分支间联系的优秀例子进一步研究 ：为相关多项式和图论问题的研究提供方法参考本文主要引用了以下关键文献：
4 M. Ledoux, Heat Flow Derivatives and Minimal Mean-Square Error in Gaussian Noise8 P. Mansanarez, G. Poly, Y. Swan, Derivatives of entropy and the MMSE conjecture9 S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph11 Ø. J. Rødseth, J. A. Sellers, and H. Tverberg, Enumeration of the degree sequences of non-separable graphs这篇论文通过严谨的数学证明，成功建立了看似无关的两个数学领域之间的深刻联系，展现了数学研究中跨学科思维的重要价值。虽然主要是理论工作，但为理解重要数学对象的组合结构提供了新的视角和方法。
