August 26
Emil Jeřábek,
Czech Academy of Sciences
Feasible reasoning with arithmetic operations
In bounded arithmetic, we study weak fragments of arithmetic that often correspond in a certain sense to computational complexity classes (e.g., polynomial time). Questions about provability in such theories can be thought of as a form of feasible reasoning: considering a natural object of interest from a complexity class $C$, can we prove its fundamental properties using only concepts from $C$?
Our objects of interest in this talk will be the elementary integer arithmetic operations $+,-,\times,/$, whose complexity class is (uniform) $\mathrm{TC}^0$, a small subclass of $\mathrm{P}$. The corresponding arithmetical theory is $\mathit{VTC}^0$. Since we do not know yet if the theory can prove the totality of division and iterated multiplication $\prod_{i<n}X_i$ which are in $\mathrm{TC}^0$ by an intricate result of Hesse, Allender, and Barrington, we will also consider an extension of the theory $\mathit{VTC}^0+\mathit{IMUL}$.
Our main question is what can $\mathit{VTC}^0\pm\mathit{IMUL}$ prove about the elementary arithmetic operations. The answer is that more than one might expect: $\mathit{VTC}^0+\mathit{IMUL}$ proves induction for quantifier-free formulas in the basic language of arithmetic ($\mathit{IOpen}$), and even induction and minimization for $\Sigma^b_0$ (sharply bounded) formulas in Buss’s language. This result is connected to the existence of $\mathrm{TC}^0$ constant-degree root-finding algorithms; the proof relies on a formalization of a form of the Lagrange inversion formula in $\mathit{VTC}^0+\mathit{IMUL}$, and on model-theoretic abstract nonsense involving valued fields.
The remaining problem is if $\mathit{VTC}^0$ proves $\mathit{IMUL}$. We will discuss issues with formalization of the Hesse–Allender–Barrington construction in $\mathit{VTC}^0$, and some partial results (this is a work in progress).