2025-11-21T06:49:15.585717

Palindromicity of the numerator of a statistical generating function

Bourn, Erickson

We prove a conjecture of Bourn and Willenbring (2020) regarding the palindromicity and unimodality of a certain family of polynomials $N_n(t)$. These recursively defined polynomials arise as the numerators of generating functions in the context of the discrete one-dimensional earth mover's distance (EMD). The key to our proof is showing that the defining recursion can be viewed as describing sums of symmetric differences of pairs of Young diagrams; in this setting, palindromicity is equivalent to the preservation of the symmetric difference under the transposition of diagrams. We also observe a connection to recent work by Defant et al. (2024) on the Wiener index of minuscule lattices, which we reinterpret combinatorially to obtain explicit formulas for the coefficients of $N_n(t)$ and for the expected value of the discrete EMD.

academic

통계 생성함수의 분자의 회문성

기본 정보

논문 ID: 2307.02652
제목: 통계 생성함수의 분자의 회문성
저자: Rebecca Bourn (University of Wisconsin–Milwaukee), William Q. Erickson (Baylor University)
분류: math.CO (조합론)
발표 시간: 2023년 7월, 최종 수정 2025년 10월 14일
논문 링크: https://arxiv.org/abs/2307.02652

초록

본 논문은 Bourn과 Willenbring (2020)이 제시한 다항식 족 $N_n(t)$ 의 회문성과 단봉성에 관한 추측을 증명한다. 이러한 재귀적으로 정의된 다항식은 이산 1차원 Earth Mover 거리(EMD) 배경에서 생성함수의 분자로 나타난다. 증명의 핵심은 정의 재귀가 Young 도형 쌍의 대칭차의 합으로 볼 수 있음을 보이는 것이다. 이 설정에서 회문성은 도형의 전치 아래에서 대칭차의 불변성과 동치이다. 저자들은 또한 Defant 등(2024)의 극소 격자 Wiener 지수에 관한 연구와의 연결을 관찰하였으며, 조합론적 재해석을 통해 $N_n(t)$ 계수와 이산 EMD 기댓값의 명시적 공식을 얻었다.

연구 배경 및 동기

문제 배경

Earth Mover 거리(EMD): 제1 Wasserstein 거리라고도 불리며, 두 히스토그램(또는 확률분포) 간의 거리를 측정한다. 한 분포를 다른 분포로 변환하는 데 필요한 최소 "작업량"을 계산한다.
통계 생성함수: 확률통계에서 생성함수는 수열 정보를 인코딩하는 중요한 도구이며, 그 분자 다항식의 성질은 종종 깊은 조합론적 의미를 갖는다.
Young 도형 이론: Young 도형은 조합수학의 기본 대상으로, 분할 이론, 표현론 등과 밀접한 관련이 있다.

연구 동기

Bourn과 Willenbring은 2020년 EMD 기댓값의 재귀 공식을 도출하였고, 생성함수 분자 $N_n(t)$ 가 회문성과 단봉성을 가지는 것으로 보인다는 것을 관찰했다.
이 관찰은 엄밀한 수학적 증명이 필요한 추측을 형성했다.
이러한 다항식의 구조를 이해하는 것은 EMD의 통계적 성질에 중요한 의미를 갖는다.

기존 방법의 한계

원래의 재귀 정의는 직관적인 조합론적 해석이 부족하다.
다항식 계수를 계산하기 위한 명시적 공식이 없다.
다른 수학 분야와의 연결이 부족하다.

핵심 기여

주요 추측 증명: 다항식 $N_n(t)$ 의 회문성과 단봉성을 완전히 증명했다.
조합론적 해석 수립: 재귀 관계를 Young 도형 대칭차의 합으로 재해석했다.
극소 격자와의 연결 발견: Defant 등의 Type A 극소 격자 Wiener 지수 연구와 연결했다.
명시적 공식 획득: $N_n(t)$ 의 계수와 이산 EMD의 기댓값에 대한 폐형식 표현을 제공했다.
재귀 문제 해결: 원래 논문의 EMD 기댓값 재귀 계산 문제를 완전히 해결했다.

방법 상세 설명

작업 정의

모든 양의 정수 $n$ 에 대해 다항식 $N_n(t)$ 가 다음을 동시에 만족함을 증명한다:

회문성: $f(t) = t^d f(1/t)$ , 여기서 $d$ 는 다항식의 전체 차수
단봉성: 계수 수열이 먼저 단조증가한 후 단조감소한다.

핵심 방법 구조

1. 대칭차의 조합론적 해석

Young 도형의 대칭차를 정의한다: $\lambda \triangle \mu := (\lambda \cup \mu) \setminus (\lambda \cap \mu)$

기호를 도입한다: $S_\triangle(a,b|c,d) := \sum_{\lambda \in \text{Par}(a \times b), \mu \in \text{Par}(c \times d)} |\lambda \triangle \mu|$

2. 주요 조합론 정리

정리 3.1: 재귀적으로 정의된 다항식 $N_{pq}(t)$ 는 명시적 표현을 갖는다: $N_{pq}(t) = \sum_{k=1}^{\min\{p,q\}} S_\triangle(k, p-k | k, q-k) \cdot t^k$

3. 회문성 증명 전략

보조정리 2.2: $S_\triangle(a,b|c,d) = S_\triangle(b,a|d,c)$

이 대칭성은 직접적으로 회문성을 도출한다: $p=q=n$ 일 때, $t^k$ 의 계수는 $t^{n-k}$ 의 계수와 같다.

4. 극소 격자와의 연결

Defant 등의 결과를 활용한다: $d(P_{a,b}) = \frac{ab}{4a+4b+2} \binom{2a+2b+2}{2a+1}$

여기서 $d(P_{a,b})$ 는 $a \times b$ 직사각형 내 Young 도형 편순서 집합의 Wiener 지수이다.

기술적 혁신점

재귀에서 조합론으로의 변환: 추상적인 재귀 관계를 구체적인 Young 도형 대칭차 계산으로 변환했다.
분야 간 연결: EMD 통계 이론과 대수 조합론(극소 격자) 사이의 다리를 구축했다.
명시화: 재귀 정의에서 폐형식 공식으로 도약하여 복잡한 재귀 계산을 회피했다.

주요 결과

정리 1.1 (주요 결과)

모든 양의 정수 $n$ 에 대해 다항식 $N_n(t)$ 는 회문이면서 동시에 단봉이다.

정리 4.1 (명시적 공식)

$N_n(t) = \frac{1}{4n+2} \sum_{k=1}^{n-1} k(n-k) \binom{2n+2}{2k+1} t^k$

정리 4.3 (EMD 기댓값)

$(\alpha, \beta) \in C(s,n) \times C(s,n)$ 이 균등하게 무작위로 선택될 때: $E[\text{EMD}(\alpha, \beta)] = \frac{s(n-1)}{4s+4n-2} \cdot \frac{\binom{2s+2n}{2s+1}}{\binom{s+n-1}{s}^2}$