組合せ論における多項式法

数学において、多項式法は、組合せ論の問題に対する代数的アプローチであり、多項式を使用して何らかの組合せ構造を捉え、その代数的特性について議論することを含む。最近、多項式法は、いくつかの長年の未解決問題に対する驚くほど単純な解決策の開発につながった。^[1] 多項式法は、組合せ論の問題を解決するために多項式と代数幾何学などの分野のアイデアを使用するための幅広い特定の手法を包含している。アロンの組合せ零点定理^[2]など、多項式法のフレームワークに従ういくつかの手法は1990年代から知られていたが、多項式法のより広範なフレームワークが開発されたのは2010年頃になってからであった。

多項式法の多くの用途は、同じ高レベルのアプローチに従います。アプローチは次のとおりです。

• いくつかの組み合わせ問題をベクトル空間に埋め込みます。
• 特定の集合上でゼロとなる低次多項式を構築することで、問題の仮説を捉える
• 多項式を構築した後、その代数的特性について議論し、元の構成が目的の特性を満たしている必要があることを推論します。

例として、多項式法を用いたDvirの有限体Kakeya予想の証明の概要を示します。 ^[3]

有限体カケヤ予想: を元を持つ有限体とします。をカケヤ集合とします。つまり、各ベクトルに対して、直線 を含むようなものが存在するとします。すると、集合のサイズは少なくとも になります。ここで はのみに依存する定数です。 ${\displaystyle \mathbb {F} _{q}}$${\displaystyle q}$${\displaystyle K\subseteq \mathbb {F} _{q}^{n}}$${\displaystyle y\in \mathbb {F} _{q}^{n}}$${\displaystyle x\in \mathbb {F} _{q}^{n}}$${\displaystyle K}$${\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}}$${\displaystyle K}$${\displaystyle c_{n}q^{n}}$${\displaystyle c_{n}>0}$${\displaystyle n}$

証明: ここで示す証明は、の大きさが少なくとも であることを示します。 の境界は、少しの追加作業で同じ方法を使用して取得できます。 ${\displaystyle K}$${\displaystyle c_{n}q^{n-1}}$${\displaystyle c_{n}q^{n}}$

次のようなカケヤ集合があると 仮定します。${\displaystyle K}$

${\displaystyle |K|<{q+n-3 \choose n-1}}$

ちょうど 次 の形式の単項式の集合を考えます。そのような単項式はちょうど 個存在します。したがって、内のすべての点でゼロになる次 の非ゼロ同次多項式が存在します。 これは、そのような多項式を見つけることが、係数について線形方程式 の連立を解くことに帰着するためであることに注意してください。${\displaystyle x_{1}^{d_{1}}x_{2}^{d_{2}}\dots x_{n}^{d_{n}}}$${\displaystyle q-2}$${\displaystyle {q+n-3 \choose n-1}}$ ${\displaystyle P(x_{1},x_{2},\dots ,x_{n})}$${\displaystyle q-2}$${\displaystyle K}$${\displaystyle |K|}$

ここで、 がカケヤ集合であるという性質を利用して、のすべてで が消える必要があることを示します。明らかに です。次に、 に対して、直線がに含まれるが存在します。は同次であるため、ある に対してであれば、任意の に対して となります。特に ${\displaystyle K}$${\displaystyle P}$${\displaystyle \mathbb {F} _{q}^{n}}$${\displaystyle P(0,0\dots ,0)=0}$${\displaystyle y\neq 0}$${\displaystyle x}$${\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}}$${\displaystyle K}$${\displaystyle P}$${\displaystyle P(z)=0}$${\displaystyle z\in \mathbb {F} _{q}^{n}}$${\displaystyle P(cz)=0}$${\displaystyle c\in \mathbb {F} _{q}}$

${\displaystyle P(tx+y)=P(t(x+t^{-1}y))=0}$

すべての非ゼロ に対して です。しかし、は の次数 の多項式ですが、の非ゼロ要素に対応する根を少なくとも 個持っているため、 は必ず 0 になります。特に、 を代入すると が導かれます。 ${\displaystyle t\in \mathbb {F} _{q}}$${\displaystyle P(tx+y)}$${\displaystyle q-2}$${\displaystyle t}$${\displaystyle q-1}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle t=0}$${\displaystyle P(y)=0}$

我々は、すべての変数について、ただし各変数の次数が より小さいことを示したので、これはシュワルツ・ジッペルの補題により不可能である。我々は、実際には ${\displaystyle P(y)=0}$${\displaystyle y\in \mathbb {F} _{q}^{n}}$${\displaystyle P}$${\displaystyle q-1}$

${\displaystyle |K|\geq {q+n-3 \choose n-1}\sim {\frac {q^{n-1}}{(n-1)!}}}$

多項式法のバリエーションである多項式分割法は、グースとカッツがエルデシュの異なる距離問題の解決に導入した。^[4]多項式分割法では、多項式を使用して基礎空間を領域に分割し、分割の幾何学的構造について議論する。これらの議論は、さまざまな代数曲線間の接続数を制限した代数幾何学の結果に依存している。多項式分割法は、多項式ハムサンドイッチ定理を介してセメレディ・トロッター定理の新しい証明を与えるために使用され、接続幾何学のさまざまな問題に適用されている。^{[5] [6]}

多項式法を使用して解決された長年の未解決問題の例をいくつか示します。

• 有限体カケヤ予想^[3] by Dvir
• エレンバーグとギスウィットによるキャップセット問題[ 7 ^]と、クルート、レフ、パックによる類似の問題に基づいて開発されたオリジナルのフレームワーク^[8]${\displaystyle \mathbb {Z} _{4}^{n}}$
• グースとカッツによるエルデシュの異なる距離問題^[4]
• 3Dにおけるジョイント問題、グースとカッツ著^[9] 。彼らの議論は後にエレケス、カプラン、シャリルによって簡略化された^[10]。

• 組み合わせゼロ設定

• 多項式法に関する調査 (Terence Tao 著)
• ラリー・ガスによる多項式法の概観