Journal of the American Mathematical Society

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degree-four polynomials, the classical sum-of-squares problem: find the smallest n n such that there exists an identity ( 0.1 ) ( x 1 2 + x 2 2 + ⋯ + x k 2 ) ⋅ ( y 1 2 + y 2 2 + ⋯ + y k 2 ) = f 1 2 + f 2 2 + ⋯ + f n 2 , \begin{equation*} (0.1)\quad \quad (x_1^2+x_2^2+\cdots + x_k^2)\cdot (y_1^2+y_2^2+\cdots + y_k^2)= f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} , \quad \quad \end{equation*} where each f i = f i ( X , Y ) f_{i} = f_i(X,Y) is a bilinear form in X = { x 1 , … , x k } X=\{x_{1},\dots ,x_{k}\} and Y = { y 1 , … , y k } Y=\{y_{1},\dots , y_{k}\} . Over the complex numbers, we show that a sufficiently strong superlinear lower bound on n n in (0.1), namely, n ≥ k 1 + ϵ n\geq k^{1+\epsilon } with ϵ > 0 \epsilon >0 , implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent.

More generally, we consider such sum-of-squares identities for any biqua- dratic polynomial h ( X , Y ) h(X,Y) , namely ( 0.2 ) h ( X , Y ) = f 1 2 + f 2 2 + ⋯ + f n 2 . \begin{equation*} (0.2) \quad \quad \qquad \quad \quad \quad \quad h(X,Y) = f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} . \quad \quad \qquad \quad \quad \quad \quad \end{equation*} Again, proving n ≥ k 1 + ϵ n\geq k^{1+\epsilon } in (0.2) for any explicit h h over the complex numbers gives an exponential lower bound for the non-commutative permanent. Our proofs rely on several new structure theorems for non-commutative circuits, as well as a non-commutative analog of Valiant’s completeness of the permanent.

We prove such a superlinear bound in one special case. Over the real numbers, we construct an explicit biquadratic polynomial h h such that n n in (0.2) must be at least Ω ( k 2 ) \Omega (k^{2}) . Unfortunately, this result does not imply circuit lower bounds. We also present other structural results about non-commutative arithmetic circuits. We show that any non-commutative circuit computing an ordered non-commutative polynomial can be efficiently transformed to a syntactically multilinear circuit computing that polynomial. The permanent, for example, is ordered. Hence, lower bounds on the size of syntactically multilinear circuits computing the permanent imply unrestricted non-commutative lower bounds. We also prove an exponential lower bound on the size of a non-commutative syntactically multilinear circuit computing an explicit polynomial. This polynomial is, however, not ordered and an unrestricted circuit lower bound does not follow.

We consider the motion of the interface of a 3-D inviscid, incompressible, irrotational water wave, with air region above water region and surface tension zero. We prove that the motion of the interface of the water wave is not subject to Taylor instability, as long as the interface separates the whole 3-D space into two simply connected C 2 C^{2} regions. We prove further the existence and uniqueness of solutions of the full 3-D water wave problem, locally in time, for any initial interface that separates the whole 3-D space into two simply connected regions.

We prove elimination of hyperimaginaries in supersimple theories. This means that if an equivalence relation on the set of realisations of a complete type (in a supersimple theory) is defined by a possibly infinite conjunction of first order formulas, then it is the intersection of definable equivalence relations.

This work proves the global stability of the Boltzmann equation (1872) with the physical collision kernels derived by Maxwell in 1866 for the full range of inverse-power intermolecular potentials,r−(p−1)r^{-(p-1)}withp>2p>2, for initial perturbations of the Maxwellian equilibrium states, as announced in an earlier paper by the authors. We more generally cover collision kernels with parameterss∈(0,1)s\in (0,1)andγ\gammasatisfyingγ>−n\gamma > -nin arbitrary dimensionsTn×Rn\mathbb {T}^n \times \mathbb {R}^nwithn≥2n\ge 2. Moreover, we prove rapid convergence as predicted by the celebrated BoltzmannHH-theorem. Whenγ≥−2s\gamma \ge -2s, we have exponential time decay to the Maxwellian equilibrium states. Whenγ>−2s\gamma >-2s, our solutions decay polynomially fast in time with any rate. These results are completely constructive. Additionally, we prove sharp constructive upper and lower bounds for the linearized collision operator in terms of a geometric fractional Sobolev norm; we thus observe that a spectral gap exists only whenγ≥−2s\gamma \ge -2s, as conjectured by Mouhot and Strain. It will be observed that this fundamental equation, derived by both Boltzmann and Maxwell, grants a basic example where a range of geometric fractional derivatives occur in a physical model of the natural world. Our methods provide a new understanding of the grazing collisions in the Boltzmann theory.

We compute the characters of the finite dimensional irreducible representations of the Lie superalgebragl(m|n)\mathfrak {gl}(m|n), and determineExt{\operatorname {Ext}}’s between simple modules in the category of finite dimensional representations. We formulate conjectures for the analogous results in categoryO\mathcal O. The combinatorics parallels the combinatorics of certain canonical bases over the Lie algebragl(∞)\mathfrak {gl}(\infty ).

If S S is a smooth compact surface in R 3 \mathbb {R}^3 with strictly positive second fundamental form, and E S E_S is the corresponding extension operator, then we prove that for all p > 3.25 p > 3.25 , ‖ E S f ‖ L p ( R 3 ) ≤ C ( p , S ) ‖ f ‖ L ∞ ( S ) \| E_S f\|_{L^p(\mathbb {R}^3)} \le C(p,S) \| f \|_{L^\infty (S)} . The proof uses polynomial partitioning arguments from incidence geometry.

A Kakeya set is a subset of F n \mathbb {F}^n , where F \mathbb {F} is a finite field of q q elements, that contains a line in every direction. In this paper we show that the size of every Kakeya set is at least C n ⋅ q n C_{n} \cdot q^{n} , where C n C_{n} depends only on n n . This answers a question of Wolff.