技術要約：幾何学的 $L_p$-不一致性における計算可能性（Tractability）対 次元の呪い

1. 問題設定

本論文は、高次元における幾何学的 $L_p$-不一致性（geometric $L_p$-discrepancies）の計算複雑性を調査している。具体的には、アンカー付き（スターおよび中心型）、アンカーなし（極値型）、および周期的な不一致性を含む、様々な不一致性の概念における「次元の呪い」対「計算可能性（tractability）」を扱っている。

中心となる指標は、初期の不一致性を $\varepsilon$ の係数で減少させるために必要な最小の点数 $N$ である 情報複雑性 $N^{\bullet}_{\text{disc}}(\varepsilon, d)$ である。問題は、この複雑性が $d \to \infty$ および/または $\varepsilon \to 0$ に対してどのように増大するかを問うものである。

• 次元の呪い（Curse of Dimensionality）: 固定された $\varepsilon > 0$ に対して、$N^{\bullet}_{\text{disc}}(\varepsilon, d)$ が $d$ に対して指数関数的に増大する場合に発生する。
• 計算可能性（Tractability）: 増大が劣指数的（例：$d$ および $\varepsilon^{-1}$ に関する多項式）である場合に発生する。

本研究では、点集合の重みのタイプとして、任意の実数重み、非負重み（$+$）、および準モンテカルロ（QMC）重み（$qmc$）の3種類を検討している。

2. 手法

著者らは、統一された 不一致性–積分双対性（discrepancy–integration duality） フレームワークを採用している。このアプローチは、ある点集合の幾何学的不一致性と、特定のノルム空間における線形求積則の最悪ケース誤差との間の等価性を確立するものである。

2.1 不一致性–積分双対性

与えられた不一致性 $D_N(P, A)$ に対して、著者らは、線形則 $Q_{P,A}$ の最悪ケース誤差が不一致性に等しくなるような関数空間 $F_d$ を特定する：
$$e(Q_{P,A}; F_d) = D_N(P, A)$$
この双対性により、幾何学的不一致性の問題を、情報ベース計算量（IBC）のツールを適用可能な積分問題へと翻訳することが可能になる。

2.2 下界法（次元の呪い）

次元の呪いを証明するために、本論文はテンソル積の仮定に基づく一般的な下界法（定理1）を利用している。この手法には以下の条件が必要である：

1. テンソル積構造: 積関数のノルムが、その構成要素のノルムの積によって抑えられること。
2. 初期誤差の因子分解: 次元 $d$ における初期誤差が、次元 1 における初期誤差の $d$ 乗であること。
3. 特定の関数の存在: 定数 $A > 1$ および $B > 1$ を含む特定の積分およびノルムの不等式を満たす、「最悪ケース」の関数 $h$ と「スプライン様」の関数族 $s_y$ の存在。

これらの条件が満たされる場合、情報複雑性は、ある $C > 1$ に対して $N^+_{\text{int}}(\varepsilon, d) \ge C^d(1-2\varepsilon)$ を満たし、非負重みに対する次元の呪いが証明される。

3. 主要な貢献と結果

3.1 アンカー付きおよび象限不一致性

本論文は、$a$-象限および $a$-アンカー付き不一致性（これにはスターおよび中心型の不一致性が特殊なケースとして含まれる）を分析している。

• 双対性: 定理3は、$a$-象限 $L_p$-不一致性と、空間 $W^1_{a,q}$（アンカー $a$ で値が消滅し、導関数が $L_q$ に属する関数）における積分との間の双対性を確立している。
• 次元の呪い:
  • $p \in (1, \infty)$ かつ $a \in \{0, 1\}$（スター不一致性）の場合、非負重みに対して次元の呪いが成立する。
  • $p \in [1, \infty)$ かつ $a \in (0, 1)$ の場合、次元の呪いが成立する。
  • $p = \infty$ かつ $a = 1/2$（中心型）の場合、次元の呪いが成立する。
• 計算可能性:
  • $p = \infty$ かつ $a \in \{0, 1\}$（スター $L_\infty$）の場合、問題は多項式的に計算可能である（$N \le C d \varepsilon^{-2}$）。
  • 「中間的」なケースである $p = \infty$ かつ $a \in (0, 1) \setminus \{1/2\}$ の場合、問題は多項式的には計算可能ではないが、完全な次元の呪いには陥らない（固定された $\varepsilon$ に対して複雑度は多項式である）。

3.2 アンカーなしの不一致性

本論文は、極値型および周期的な不一致性を検証している。

• 極値不一致性（Extreme Discrepancy）:
  • 双対性: 定理4は、極値 $L_p$-不一致性を、$L_q(D_d)$ 上の線形作用素によって定義される空間における積分へと結びつけている。
  • 結果: $p \in (1, \infty)$ に対して次元の呪いが成立する。$p = \infty$ の場合、問題は多項式的に計算可能である。
• 周期的不一致性（新しい結果）:
  • 双対性: 定理6は、一般的な $p, q$ に対する新しい双対性を提供し、周期的な積分作用素を介して定義される空間 $F^{per}_{d,q}$ における積分と周期 $L_p$-不一致性を結びつけている。
  • 次元の呪い: 定理7は、すべての $p \in (1, \infty)$ において、非負重みを持つ周期 $L_p$-不一致性が次元の呪いに陥ることを証明している。これは、これまで $p=2$ のみで知られていた先行研究の結果を拡張するものである。
  • 計算可能性: $p = \infty$ の場合、周期的不一致性は多項式的に計算可能である（具体的には $N \le C d \log(d+1) \varepsilon^{-2}$）。

3.3 オープンな問題の要約

本論文は、$L_1$-不一致性 の挙動を現在の知識における主要な空白として明示的に特定している。

• 未解決問題: スター、極値、または周期的な $L_1$-不一致性が次元の呪いに陥るかどうかは、依然として証明されていない。現在の手法は $p > 1$（具体的には、特定の最悪ケース関数と、$1/p + 1/q = 1$ を満たすヘルダー共役 $q$ の存在）に依存している。

4. 意義と範囲

本論文の主な意義は、幾何学的不一致性の計算可能性に関する体系的な概観と統一的な枠組みを提供することにある。

• 統一: 分散した様々な出版物の結果を、不一致性–積分双対性を用いて単一の首尾一貫した構造へと統合している。
• 新しい証明: 以前の文献では部分的または特定のケースしか提供されていなかった一般的な設定（例：一般的な $a$ および $p$ を持つアンカー付き不一致性）に対して、完全な証明を提供している。
• 新しい洞察: 周期 $L_p$-不一致性に関する新しい結果（$p \in (1, \infty)$）を提示し、「中間的」なアンカー付き $L_\infty$ ケースの計算可能性の状態を明確にしている。
• 限界: 著者らは、彼らの下界法（定理1）が現在のところ $L_1$ のケースには適用できないことを謙虚に述べており、$L_1$-不一致性の問題がこの分野における主要な未解決問題として残されている。

本論文は、$p \in (1, \infty)$ における $L_p$-不一致性にとって次元の呪いが一般的な現象である一方で、$p=1$ および $p=\infty$ の挙動は、不一致性の具体的な種類や重みの選択によって大きく異なることを結論づけている。