Recogntion of Algebraic Matroids is Undecidable
20 hours ago
- Boege和Yashfe证明了代数拟阵的识别问题是不可判定的，结合了拟阵理论、代数几何、模型论和不可判定性。
- 在特征零情况下，每个代数拟阵在适当的扩域上是线性的（Ingleton, 1971），这使得识别问题可判定，但在正特征下，代数拟阵不一定是线性的。
- 不存在算法可以判定有限拟阵在任意给定的正特征下是否为代数拟阵，也无法判定它在没有特征限制的某个域上是否为代数拟阵。
- 该证明使用了经典的von Staudt构造、Hrushovski-Zilber群配置定理，并通过拟阵信息识别Frobenius映射，最终将有理函数域上的方程转化为拟阵可实现性问题。
- 此类域上方程的不可判定性通过Pheidas（奇特征）和Videla（特征2）的结果得以确立。
- Vámos拟阵是一个非代数拟阵的例子：在8个元素上秩为4，有五个依赖的4元集（circuit-hyperplanes），但有一个明显的独立4元集，违反了代数拟阵的性质。