combinatorial designの構成

集合族$\mathcal{S}$であって任意の相異なる二つの元の共通部分が小さいものを平均計算量理論の文脈でcombinatorial designと呼ぶことがあり, 擬似乱数生成器の構成などにおいて非常に重要な役割を果たします. 具体的には, 台集合$E$上の集合族$\mathcal{S}$であって以下を満たすものを($E$上の)$(d,n)$-designと呼びます.

• 各$S\in\mathcal{S}$に対して$|S|=n$.
• 各$S\neq T\in \mathcal{S}$に対して$|S\cap T|\leq d$.

例1. グリッド

台集合$E=[m]^2$上の集合$S_i=\{(x,y)\in E\colon x=i\text{ or }y=i\}$を考えると $\mathcal{S}=\{S_i\}_{i\in[m]}$は$(2,2m-1)$-designになります.

本記事では$(d,n)$-designの応用先には特に触れず, [NW94]で与えられた以下の$(d,n)$-designを紹介します. Nisan--Wigderson Generatorを知っていても具体的なcombinatorial designを知らない人向けの備忘録です.

定理 (Lemma 2.4 of [NW94]).

各素べき$n$と$d\in\mathbb{N}$に対して, $|E|=n^2$かつ$|\mathcal{S}|=n^{d+1}$を満たす台集合$E$上の$(d,n)$-designが存在する.

証明.

有限体$\mathbb{F}_n$を考え, $E=\mathbb{F}_n^2$とします. $\mathcal{P}_{\leq d}$を$\mathbb{F}_n$上の次数高々$d$の多項式全体の集合とし, 各$p\in\mathcal{P}_{\leq d}$に対して$S_p=\{(x,p(x))\colon x\in \mathbb{F}_n\}$とし, $\mathcal{S}=\{S_p\}_{p\in\mathcal{P}_{\leq d}}$とします. 明らかに$|\mathcal{S}|=|\mathcal{P}_{\leq d}|=n^{d+1}$です.

上で与えた$\mathcal{S}$が確かに$(d,n)$-designになっていることを確認します. まず, 各$S\in\mathcal{S}$は$n$個の点の集合なので確かに$|S|=n$を満たします. 次に$|S_p\cap S_q|>d$を満たす相異なる二つの多項式$p,q\in\mathcal{P}_{\leq d}$が存在すると仮定します. このとき, $p(x)=q(x)$を満たす$x\in\mathbb{F}_n$が$d+1$個以上存在することになりますが, このとき多項式$p-q$は次数高々$d$で$d+1$個の点で$0$になるので, 恒等的に$0$となり, $p\neq q$と矛盾します.

(証明終)

参考文献

[NW94] N. Nisan and A. Wigderson, Hardness vs Randomness, JCCS, 1994.