Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erd\H{o}s Problem #272)

技術要約：算術級数の共通部分を持つ整数の族に関する厳密な値と厳密な上界

問題設定
本論文は、Erdős Problem #272に取り組んでいる。この問題は、$t(N)$ という関数を決定することを目的としている。ここで $t(N)$ とは、$\{1, \dots, N\}$ の相異なる部分集合 $A_1, \dots, A_t$ の最大個数であり、任意の異なる 2 つの集合の共通部分 $A_i \cap A_j$ が空でない算術級数（AP）となるものである。

歴史的に、Simonovits と Sós は $t(N) = O(N^2)$ であることを示し、最大値は「ある固定された要素を含むサイズ3以下のすべての部分集合」の族によって達成されるという、$\binom{N}{2} + 1$ という予想を立てた。その後、Szabó は $t(N) \ge \binom{N}{2} + 1 + \lfloor (N-1)/4 \rfloor$ を達成する族を構成することで、この厳密性に関する予想を覆した。さらに Szabó は、$t(N) = N^2/2 + O(N^{5/3}(\log N)^3)$ という漸近的挙動を確立し、次の 2 つの重要な問いを提起した。(i) $t(N) = \binom{N}{2} + O(N)$ かどうか、および (ii) 「カーネル問題」：すべての極大族（最大値を達成する族）は、そのすべての集合に共通して含まれる要素を持つ必要があるのか、という問いである。

手法
著者らは、徹底的な計算検証、構造的組合せ論、および解析的な境界推定を組み合わせたハイブリッド・アプローチを採用している。

1. 厳密な計算： 小規模な $N$ ($N \le 12$) に対して、問題は、頂点が $[N]$ の空でない部分集合であり、エッジが非空の AP 共通部分を持つ集合同士を結ぶグラフにおける最大クリークを見つける問題としてモデル化される。
   • $N \le 10$ では、貪欲な彩色境界を用いたビット並列分枝限定法ソルバーが使用された。
   • $N = 11$ および $12$ では、ルート分解、次数減少順序、コア・ピーリング、および厳密な「スター・プルーニング（星型枝刈り）」ステップを利用した決定探索が用いられ、より大きな族が存在しないことが証明された。
2. 構造的分解： 一般的な上界の証明は、「スター型」の族（共通の要素 $m$ を持つ族）を、サイズ $\le 2$、サイズ $3$、およびサイズ$\ge 4$ の部分集合へと分解することに基づいている。
3. 欠損1の計数不等式（Defect-One Counting Inequality）： 中心的な技術的ツールは、「階段状領域」（0 を含む整数の区間の族）に関する計数不等式である。著者らは、そのような族において、メンバーの数は「悪いペア」（$\{0, u, v\}$ が AP にならないペア $\{u, v\}$）がカバーする数に、小さな欠損項を加えたものによって抑えられることを証明している。これは、パラメータ 500 までの正確な動的計画法による検証と、より大きなパラメータに対する正定値二次形式を用いた漸近的な議論によって検証されている。
4. プライベート・ペア定理（Private-Pair Theorem）： 「歪んだ（crooked）」メンバー（AP ではないサイズ $\ge 4$ の集合）は、その家族内の他のどのメンバーにも含まれない要素のペアである「プライベートな悪いペア」を必ず含むという構造定理が確立されている。これにより、非 AP メンバー間での「キル（悪いペア）」の共有が防止され、タイトな計数境界が可能となる。

主な貢献および結果

• 小規模な $N$ に対する厳密な値： 本論文は、$N = 3, \dots, 12$ における $t(N)$ を正確に決定している。その値は $4, 7, 12, 17, 23, 30, 39, 48, 58, 69$ である。この全範囲において、Szabó の下限は厳密である。この数列は現在 OEIS には掲載されていない。
• 精緻化された予想： 計算的証拠に基づき、著者らはすべての $N \ge 1$ に対して次のように予想している：
  $$t(N) = \binom{N}{2} + 1 + \left\lfloor \frac{N-1}{4} \right\rfloor$$
  これは、Szabó の漸近的な問いを、厳密な公式へと精緻化したものである。
• スター型族に対する厳密な上界： 主要な理論的結果（定理 1.4）は、任意の「スター型」の族（すべての集合が共通の要素を共有するもの）において、そのサイズが Szabó の下限によって抑えられることを証明している。これは、$N \ge 5$ に対して知られている、この種の最初の厳密な上界である。
  • 証明は、「欠損1」の計数不等式と「プライベート・ペア定理」を組み合わせ、非 AP メンバーを処理する手法を用いている。
• カーネル問題への帰着： 著者らは、精緻化された予想（この公式がすべての $N$ で成立するという点）が、Szabó のカーネル予想（すなわち、すべての極大族はスター型であるという説）が真であれば直ちに導かれることを示している。したがって、$t(N)$ を正確に決定する問題は、極大族が共通の要素を持つことを証明するという問題へと帰着される。
• 反例に対する構造的制約： 本論文は、非スター型の極大族（カーネル予想の反例となるもの）の仮説的な構造を分析している。もしそのような族が存在する場合、その 3 要素集合（triples）は共通の要素を共有し、その要素を避けるメンバーは、公差が小さい長い算術級数になることを証明している。著者らは、このような構成は「自己制限的」であり、予想される境界に達することは困難であると論じているが、完全な証明は未解決のままである。

意義
本論文は、$t(N)$ の（特に $N \le 12$ における）最初の厳密な決定を提供し、制限されたクラスであるスター型族に対する最初の厳密な上界を確立したと主張している。すべてのスター型族において下限が厳密であることを証明することで、本研究は、Erdős Problem #272 を完全に解決するための唯一の残された障害が「カーネル特性」であることを浮き彫りにした。著者らは、自らの結果が、共通の要素を共有する族のクラスにおいて Szabó の構成が最適であることを裏付けていると述べており、また、欠損1の計数不等式やプライベート・ペア定理といった、他の交差問題にも適用可能な新しい組合せ論的手法を導入している。