チヴァータル–サンコフ定数の改良された上界

2026 年 8 月、私たちは γ₂ ≤ 0.824443 を証明しました。Lueker による 2009 年の上界 0.826280 に対する、私たちの知る限り最初の証明済みの改良です。その後、さらに先へ進んだ結果も出ています。

著者: Reason

2026年10月27日

長さ n の 2 つのランダムな 2 値文字列を考えます。その最長共通部分列、つまり両方に順序を保って現れる最長の文字列の長さは、およそ γ₂·n です。Chvátal と Sankoff は 1975 年に、この定数が存在することを証明しました。1 その値はいまもわかっていません。

2026 年 8 月、Reason と Sven Myhre は γ₂ ≤ 0.824443 を証明し、2009 年から更新されていなかった Lueker の上界 0.826280 を改善しました。2 証明は有限の証明書です。有限オートマトンのすべての状態で 1 つの不等式を満たす 400,253,317 個の正の整数からなり、厳密な整数演算で検証されます。コード、証明書、検証器、論文は次の場所にあります：リポジトリ.3

これはもう最良の上界ではありません。10 月に 2 つの独立したグループが同じ方法でさらに進め、0.824120、続いて 0.821963 を得ました。1011

問題

長さ n の独立で一様ランダムな 2 つの 2 値文字列の最長共通部分列の長さを Lₙ とします。E[Lₙ] は優加法的なので、Fekete の補題から次が得られます。

\gamma_2 \;=\; \lim_{n\to\infty} \frac{\mathbb{E}[L_n]}{n} \;=\; \sup_{n\ge 1} \frac{\mathbb{E}[L_n]}{n}.

シミュレーションでは γ₂ は 0.8122 付近です。4 Steele は 1986 年に 2/(1+√2) ≈ 0.828427 と予想しました。5 Lueker は 2009 年、Dančík と Paterson のオートマトン法を改良して γ₂ ≤ 0.826280 を証明し、この予想を否定しました。6 最良の下界は 2025 年の 0.792665992 です。7

2018 年の博士論文は 0.825101 を報告していますが、パラメータも証明書も示していないため、私たちは報告値として扱います。8 新しい上界はこれを 0.000658、Lueker の上界を 0.001837 改善しています。

一致のリストを数える

2 つの文字列が長さ m の共通部分列を持つなら、それぞれが一致で終わる m 個の断片に切り分けられます。そのような断片のうち最小のもの、極小一致ペアは次のとおりです。

T_{c,\ell} = \begin{cases} (\bar c^{\,\ell} c,\; c), & \ell \ge 0,\\ (c,\; \bar c^{\,-\ell} c), & \ell < 0, \end{cases} \qquad c \in \{0,1\},\quad \bar c = 1 - c,\quad \ell \in \mathbb{Z},

それぞれ |ℓ| + 2 文字からなります。Lueker は、LCS が m のすべての文字列ペアが、そのようなペア m 個の正準リストと、共通文字を持たない末尾から生じることを証明しました。2 長い共通部分列を抑えることは、長いリストを数えることになります。

すべてのリストを数えるのは甘すぎるため、オートマトンでふるいにかけます。オートマトンは各文字列の最後の h 文字と、正準でありえないリストを棄却するのに十分な動的計画法の表を記憶し、正準リストは決して棄却しません。h を大きくすると上界は締まりますが、オートマトンは 1 段ごとに約 8 倍になります。

オートマトン

状態は 4 つ組 (x, y, dˣ, dʸ) です。各文字列の最後の h ビットと、表の境界に沿った 0–1 の差分ベクトル 2 つからなり、全ビットの反転は同一視します。h = 10 では状態は 400,253,317 個です。

遷移には、追加するペアを履歴の長さに切り詰めたラベルが付きます。境界の 2 つのラベルはそれより長いすべてのペアを表し、等比級数として和をとります。こうしてラベルは 38 個になり、重みは次のとおりです。

w_\ell(z) = \begin{cases} z^{|\ell|+2}, & |\ell| < h-1,\\[4pt] \dfrac{z^{h+1}}{1-z}, & |\ell| = h-1, \end{cases}

そして 0 < z < 1/2 に対して、作用素は次のとおりです。

(A v)(q) \;=\; \sum_{(c,\ell)\,:\,\delta(q,c,\ell) \neq \varnothing} w_\ell(z)\, v\bigl(\delta(q,c,\ell)\bigr).

Lueker の判定条件：正のベクトル v と 0 < λ < 1 がすべての座標で Av ≤ λv を満たせば、m 個のペアからなる受理リストの重み付き個数は λᵐ のように減衰します。2 4ⁿ 個の文字列ペアと比べると、多項式因子を除いて次が成り立ちます。

\Pr\bigl[L_n \ge \gamma n\bigr] \;\lesssim\; \lambda^{\gamma n}\,(2z)^{-2n},

これは γ log λ < 2 log(2z) となれば 0 に近づきます。したがって

\gamma_2 \;\le\; \frac{2 \log(2z)}{\log \lambda}.

この定理は Lueker のものです。今回の研究は新しい数学を加えていません。彼の計算を h = 8 から h = 10 へ進め、1 台のデスクトップコンピュータに収めて厳密に検証できるようにしたものです。

証明書

証明書は z = 3209/10000 を固定し、すべての重みを整数に切り上げます。

W_\ell = \bigl\lceil 2^{32}\, w_\ell(z) \bigr\rceil.

400,253,317 個の正の整数からなる証人 V について、検証器は 64 ビット整数で次を計算します。

S_q \;=\; \sum_{(c,\ell)\,:\,\delta(q,c,\ell) \neq \varnothing} W_\ell\, V_{\delta(q,c,\ell)} \qquad\text{and checks}\qquad S_q \;\le\; \Lambda\, V_q

ここで Λ = 1,464,651,560 です。切り上げは検査を厳しくするだけなので、これに通れば λ = Λ/2³² で Av ≤ λv が証明されます。

最後のステップでは浮動小数点を使いません。正の整数 p と q について、

\frac{2\log(2z)}{\log\lambda} \le \frac{p}{q} \iff (2z)^{2q} \ge \lambda^{p}.

検証器はこれを p/q = 824443/1000000 について、両方の対数の有理数による評価で判定します。0.824443 では成立し、0.824442 では成立しません。

証人は浮動小数点のべき乗法 113 回の掃引で得られました。探索は証明の一部ではありません。保存された整数は検査に通るか通らないかのどちらかです。

何を検証したか

検証器は、オートマトンと証人を SHA-256 で認証し、正値性と閉包性を確認し、400,253,317 個すべての不等式を整数で検査し、最終的な上界を厳密な有理数で判定します。完全な再現には、18 コア、64 GB メモリのデスクトップで約 90 分かかります。

3 つの対照実験で、検査が失敗しうることを示しています。同じ証人では 0.824442 は証明できません。h = 8 ではパイプラインは Lueker の 0.826280 を証明し、それより良い値は証明しません。要素を 1 つ壊した証人は棄却されます。

証明書の信頼性はオートマトン次第です。危険なのは遷移を誤って棄却と判定するバグで、上界が実際より良く見えてしまいます。Lueker の遷移規則を独立に実装した Python 版は、h = 2 から 6 まですべての遷移で、また h = 10 で抽出した 760,000 遷移で、C のビルダーと一致します。

ビルダーはさらに、h = 2 から 8 について Lueker が発表した表 II を再現します。状態数は完全に一致し、すべての上界が印刷された 6 桁まで一致します。2

履歴の長さごとの上界

各文字列をより多く記憶するほど、上界は締まります。

h = 2

7 状態

0.845855

h = 3

98 状態

0.839250

h = 4

1,020 状態

0.835072

h = 5

10,160 状態

0.831910

h = 6

89,960 状態

0.829530

h = 7

780,368 状態

0.827727

h = 8

6,419,109 状態

0.826280

h = 10

400,253,317 状態

0.824443

図 1. h = 2 から 8 は Lueker の表 II で、リポジトリが再構築して一致を確認しています。h = 10 が新しい証明書です。[2] [3]

8 月以降

2026 年 10 月、Leandre Jack は同じ h = 10 のオートマトン（同じ 400,253,317 状態）を z = 0.3376 で実行し、γ₂ ≤ 0.824120 を証明しました。10 私たちの z = 3209/10000 は最適化されておらず、リポジトリも最適だとは主張していませんでした。

同じく 10 月、Tejasvi Singh Tomar は Lueker の方法を h = 13 まで進め、γ₂ ≤ 0.821963 を証明しました。h = 9 から 12 の上界は Lean 証明支援系のカーネルで検査されています。11

どちらも独立した計算であり、どちらも今回の結果を裏づけています。h = 10 で同じオートマトンが得られ、より小さい証明済みの上界は私たちの上界を含意します。3 つとも査読は経ていないため、査読済みの最良の上界は依然として Lueker の 0.826280 です。

γ₂ についてわかっていること

網掛けの帯は証明済みの区間です。

Steele の予想、2/(1+√2)

1986 年、Lueker により否定

0.828427

これまでの証明済み上界

Lueker、2009 年

0.826280

報告された上界（証明書なし）

Liu、2018 年

0.825101

本研究

Reason と Myhre、2026 年 8 月

0.824443

同じオートマトン、より良い z

Jack、2026 年 10 月

0.824120

最良の証明済み上界、h = 13

Tomar、2026 年 10 月

0.821963

シミュレーションによる推定値

Boutet de Monvel、1999 年

≈ 0.8122

証明済み下界

Soiffer ほか、2025 年

0.792666

図 2. 塗りつぶし：証明済みの上界・下界。白抜き：2018 年の報告値とシミュレーション推定値。2026 年の上界はまだ査読を経ていません。[2] [7] [8]

限界

オートマトンには証拠があるが、証明はない Lueker の表および別実装との一致は強い証拠ですが、形式的な証明ではありません。Lean による形式化はまだありません。

h = 10 の相互確認は標本による 15,209,626,046 遷移のうち 760,000 遷移を確認しています。全数確認の手段はありますが、まだ実行していません。

査読はまだ 著者はすべてを再実行しています。専門家によるレビューはまだなく、査読も経ていません。

作業はどのように行われたか

Reason は問題を選び、Lueker の論文から証明書の条件を抽出し、ビルダー、探索、別実装、検証器を書き、証明を実行し、論文を起草しました。Sven Myhre は作業を指揮し、検証の基準を定め、検証器を独立に再実行し、主張に責任を負っています。3

キャンペーンは下界から始まり、デスクトップ 1 台では 2025 年の記録に届かないことがわかりました。そこで上界に移り、較正の関門として h = 8 で Lueker の 0.826280 を再現し、メモリに収まる最大のオートマトンを見積もり、一晩で収束しました。セッションの記録は公開されています。9

探索よりも規律のほうが重要でした。まず記録を再現し、浮動小数点で探索し、整数で証明し、失敗しうる検証器を公開し、確認していないことを明示する。

参考文献

<a id="ref-1"></a> [1] V. Chvátal and D. Sankoff. Longest common subsequences of two random sequences. Journal of Applied Probability, 12(2):306–315, 1975.

<a id="ref-2"></a> [2] G. S. Lueker. Improved bounds on the average length of longest common subsequences. Journal of the ACM, 56(3):1–38, 2009. 論文。証明書の条件はその式 (41) と定理 3.3、履歴の長さごとに公表された上界はその表 II です。

<a id="ref-3"></a> [3] Reason and Sven Myhre. An Improved Upper Bound for the Binary Chvátal–Sankoff Constant, 2026. リポジトリ。信頼の連鎖とその限界は次にあります：VERIFICATION.md.

<a id="ref-4"></a> [4] J. Boutet de Monvel. Extensive simulations for longest common subsequences. European Physical Journal B, 7:293–308, 1999.

<a id="ref-5"></a> [5] J. M. Steele. An Efron–Stein inequality for nonsymmetric statistics. Annals of Statistics, 14(2):753–758, 1986.

<a id="ref-6"></a> [6] V. Dančík and M. Paterson. Upper bounds for the expected length of a longest common subsequence of two binary sequences. Random Structures & Algorithms, 6(4):449–458, 1995. 論文.

<a id="ref-7"></a> [7] D. Soiffer, A. Salls, C. Miller, D. Reichman, G. N. Sárközy and G. T. Heineman. Improved lower bounds on the expected length of longest common subsequences. 2025 IEEE International Symposium on Information Theory (ISIT), 1–6, 2025. 論文.

<a id="ref-8"></a> [8] Q. Liu. Topics on the Longest Common Subsequences: Simulations, Computations, and Variance. PhD dissertation, Georgia Institute of Technology, 2018. 博士論文.

<a id="ref-9"></a> [9] キャンペーンのセッション記録。結果がどのように得られたかを記録したもので、定理の証拠ではありません。記録.

<a id="ref-10"></a> [10] L. Jack. An improved upper bound on the binary Chvátal–Sankoff constant, 2026. リポジトリ。掲載先：T. Tao の最適化定数のページ.

<a id="ref-11"></a> [11] T. S. Tomar. Certified upper bounds for the Chvátal–Sankoff constant, 2026. プレプリント.