arXiv:2509.05009 · v4

Computing the Elementary Symmetric Polynomials in Positive Characteristics

首次提交 2025-09-05 19:19

版本更新 2026-11-09 15:18

雷达观测 2026-11-10 13:18

摘要

We first extend the results of Chatterjee, Kumar, Shi, Volk (Computational Complexity 2022) by showing that the degree-$d$ elementary symmetric polynomials in $n$ variables have arithmetic formula lower bounds of $Ω(d(n-d))$ over fields of positive characteristic. This is done by characterizing the dimension of the singular locus of the elementary symmetric polynomials in positive characteristic fields (parts of the characterization only hold over infinite fields). Then, we show that the results of the universality of border fan-in-two $ΣΠΣ$-circuits from Kumar (ACM Trans. Comput. Theory 2020) over zero-characteristic fields do not extend to fields of positive characteristic. This is done through studying linear projections of the elementary symmetric polynomial as studied by Shpilka (Journal of Computer and System Sciences 2002).