2025-11-13T19:46:11.159766

Functional inequalities on the biased and restricted cube: an induction approach

Chang, Sun, Yu

We develop new discrete functional inequalities on the hypercube via the induction-by-restrictions method. This method reduces high-dimensional inequalities to explicit low-dimensional analytic verifications and has recently proved effective for many discrete functional inequalities. We establish two results along this framework. First, we prove a sharp $p$-biased edge-isoperimetric inequality for real-valued increasing functions, which recovers the classic biased edge-isoperimetric inequality for increasing sets and identifies increasing subcubes as the extremizers. This result also admits a probabilistic interpretation in terms of maximizing the mean first exit time of biased random walks. Second, we give an inductive proof of a PoincarÃ© inequality on increasing subsets of the cube that was recently established by Fei and Ferreira Pinto Jr, yielding an $O(n^2)$ upper bound on the mixing time of censored random walks, improving upon previous bounds.

academic

偏置および制限立方体上の関数不等式：帰納法的アプローチ

基本情報

論文ID: 2506.09852
タイトル: Functional inequalities on the biased and restricted cube: an induction approach
著者: Fan Chang, Guowei Sun, Lei Yu
分類: math.CO（組合数学）、math.PR（確率論）
発表日: 2025年10月14日（ArXiv プレプリント）
論文リンク: https://arxiv.org/abs/2506.09852

概要

本論文は、帰納的制限法（induction-by-restrictions method）を用いて超立方体上の新しい離散関数不等式を確立している。この方法は高次元不等式を明示的な低次元解析検証に簡約し、最近多くの離散関数不等式において有効であることが証明されている。本論文はこのフレームワークの下で2つの結果を確立している。第一に、実数値単調増加関数に対する鋭いp-偏置辺等周不等式を証明し、単調増加集合の古典的な偏置辺等周不等式を復元し、単調増加部分立方体を極値化子として特定している。この結果は偏置ランダムウォークの平均初回脱出時間の最大化に関する確率論的解釈も有している。第二に、最近FeiとFerreira Pinto Jr.により確立された立方体上の単調増加部分集合に対するポアンカレ不等式の帰納的証明を与え、審査ランダムウォークの混合時間に対するO(n²)上界を得て、先行する界を改善している。

研究背景と動機

問題背景

離散立方体上の関数不等式（ポアンカレ不等式、対数ソボレフ不等式、辺等周不等式など）は現代離散解析の中核をなしている。これらの不等式はブール関数解析、離散等周問題、マルコフ連鎖のスペクトル理論を結びつけ、測度集中、閾値現象、ランダムウォークの混合時間の研究に強力なツールを提供している。

既存方法の限界

古典的な均一積設定{0,1}^n上では、これらの不等式はよく理解されている：鋭い定数は既知であり、優雅な証明はテンソル化、半群法、または離散フーリエ解析を通じて得られている。しかし、積設定から逸脱すると——構造化部分集合への制限を通じて、または偏置測度の下で作業する場合——古典的方法はしばしば失効するか、鋭さを失う。

具体的な課題

偏置測度下の不等式：均一立方体上では、対数ソボレフ不等式は一般的な実数値関数に対して鋭いが、指示関数に特化すると、辺等周界の次最適乗法定数（1/ln 2の因子差）のみを復元できる。
審査ランダムウォーク：{0,1}^n上の単純ランダムウォークを部分集合Aに審査すると、チェーンは非積空間に存在し、その幾何学はAの境界によって決定される。積ベースの標準ツール（テンソル化、フーリエ分解）はもはや明確に適用されない。

研究動機

本論文は帰納的制限法を通じて非積環境に適応した新しい離散関数不等式を確立することを目指しており、特に以下に焦点を当てている：

p-偏置立方体上のサモロドニツキー型関数不等式の確立
審査ランダムウォークの混合時間問題に対するより簡潔な証明方法の提供

核心的貢献

p-偏置辺等周不等式：実数値単調増加関数に対する鋭いp-偏置辺等周不等式を確立し、単調増加集合の鋭いp-偏置等周不等式を復元し、偏置ランダムウォークの平均初回脱出時間に関する確率論的解釈を提供している。
単調増加集合上のポアンカレ不等式：FeiとFerreira Pinto Jr.により最近確立された単調増加集合に対するポアンカレ不等式のより簡潔な帰納的証明を与え、審査ランダムウォークの混合時間に対するO(n²)上界を得ている。
方法論的貢献：非積環境における帰納的制限法の有効性を示し、高次元関数不等式を体系的に有限次元検証に簡約している。
理論的洞察：単調増加部分立方体を複数の最適化問題の極値化子として特定し、関数不等式とランダムウォーク理論の間に新しい関連性を確立している。

方法の詳細説明

帰納的制限法フレームワーク

帰納的制限法は以下のステップで機能する：

関数fを制限関数g₀とg₁に分解する（最後の座標を固定することで得られる）
g₀とg₁を用いてディリクレ形式と分散を再帰的に表現する
次元n-1で帰納法の仮定を適用する
明示的な2点（または多点）不等式の検証を通じて残りの交差項を制御する

p-偏置辺等周不等式の証明

タスク定義

p-偏置測度μₚと単調増加関数g：{0,1}ⁿ→ℝに対して、以下を証明する： $p \cdot E_p(g,g) \geq \frac{E_p[|g|]^2}{\mu_p(A)} \log_p \mu_p(A)$

ここでEₚ(g,g)はディリクレ形式、Aはgの台集合である。

主要な技術的ステップ

ステップ1：関数分解 関数gを以下のように分解する：

g₀(x')：= g(x',0)
g₁(x')：= g(x',1)

ここでx'は最初のn-1個の座標を表す。

ステップ2：ディリクレ形式の分解 補題2.3を使用する： $E_p^n(g,g) = pE_{p}^{n-1}(g_1,g_1) + (1-p)E_{p}^{n-1}(g_0,g_0) + \|g_1-g_0\|_{2,\mu_p}^2$

ステップ3：帰納法の仮定の適用 次元n-1で帰納法の仮定を適用する： $pE_{p}^{n-1}(g_1,g_1) \geq \frac{E_p[g_1]^2}{a_1}\log_p a_1$ $pE_{p}^{n-1}(g_0,g_0) \geq \frac{E_p[g_0]^2}{a_0}\log_p a_0$

ステップ4：2点不等式の検証 重要なのは以下の2点不等式を検証することである： $pf(a_1) + (1-p)f(a_0) + (1-p)a_1f(a_0)f(a_1) \geq ((1-p)a_1f(a_0) + (1-p)^2a_1f(a_1) + 1)f(pa_1 + (1-p)a_0)$

ここでf(t) = (log_p t)/tである。

ポアンカレ不等式の証明

タスク定義

単調増加集合A ⊆ {0,1}ⁿと関数f：A→ℝに対して、以下を証明する： $\text{Var}_A[f] \leq \frac{2}{1-\sqrt{1-\mu(A)}} \cdot E_A(f)$

技術的革新点

簡潔な帰納フレームワーク：FeiとFerreira Pinto Jr.の複雑な方向付き熱流法と比較して、本論文は帰納法に基づいた簡潔な証明を提供している
5点不等式：高次元問題を検証可能な5点不等式に簡約する
定数の最適化：定数は1から2に変わるが、方法はより直接的で理解しやすい