Polynomial rank-bound conjecture for depth-four identities

Let KK be a field of characteristic ch(K)\operatorname{ch}(K), and let Rδ(k,s)R_{\delta}(k,s) strictly upper-bound the rank of any minimal and simple ΣΠδΣΠ(k,s,n)\Sigma\Pi_{\delta}\Sigma\Pi(k,s,n) identity, where the rank is the transcendence degree over KK of the set of sparse polynomials in the circuit. The known constructions give lower bounds Rδ(k,s)=Ω(δk)R_{\delta}(k,s)=\operatorname{\Omega}(\delta k) when ch(K)=0\operatorname{ch}(K)=0 and Rδ(k,s)=Ω(δklogps)R_{\delta}(k,s)=\operatorname{\Omega}(\delta k\log_p s) when ch(K)=p>0\operatorname{ch}(K)=p>0. Rank-bound conjecture.

Rδ(k,s)={poly(δk),if ch(K)=0,poly(δklogs),otherwise.R_{\delta}(k,s)= \begin{cases} \operatorname{poly}(\delta k), & \text{if $\operatorname{ch}(K)=0$},\\ \operatorname{poly}(\delta k\log s), & \text{otherwise}. \end{cases}

This conjecture would give polynomial upper bounds on the rank parameter governing minimal and simple depth-four identities, a quantity central to deterministic blackbox identity testing. The source does not provide a resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Malte Beecken, Johannes Mittmann and Nitin Saxena, “Algebraic Independence and Blackbox Identity Testing”, arXiv:1102.2789 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.