An official website of the United States government
On the Rational Degree of Boolean Functions and Applications Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions f, it is conjectured that rdeg(f) is polynomially related to deg(f), where deg(f) is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least deg(f)/2 and monotone functions have rational degree at least sqrt(deg(f)). We observe that both of these lower bounds are tight. In addition, we show that all read-once depth-d Boolean formulae have rational degree at least Ω(deg(f)1/d). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2−O(sqrt(n)). In contrast to total functions, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model.
more »
« less
Proof of the elliptic expansion moonshine conjecture of Căldăraru, He, and Huang
Using predictions in mirror symmetry, Căldăraru, He, and Huang recently formulated a “Moonshine Conjecture at Landau-Ginzburg points” [arXiv:2107.12405, 2021] for Klein’s modular j j -function at j = 0 j=0 and j = 1728. j=1728. The conjecture asserts that the j j -function, when specialized at specific flat coordinates on the moduli spaces of versal deformations of the corresponding CM elliptic curves, yields simple rational functions. We prove this conjecture, and show that these rational functions arise from classical 2 F 1 _2F_1 -hypergeometric inversion formulae for the j j -function.
more »
« less
- Award ID(s):
- 2055118
- PAR ID:
- 10404466
- Date Published:
- Journal Name:
- Proceedings of the American Mathematical Society
- Volume:
- 150
- Issue:
- 12
- ISSN:
- 0002-9939
- Page Range / eLocation ID:
- 5047-5056
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We generalize Hermite interpolation with error correction, which is the methodology for multiplicity algebraic error correction codes, to Hermite interpolation of a rational function over a field K from function and function derivative values. We present an interpolation algorithm that can locate and correct <= E errors at distinct arguments y in K where at least one of the values or values of a derivative is incorrect. The upper bound E for the number of such y is input. Our algorithm sufficiently oversamples the rational function to guarantee a unique interpolant. We sample (f/g)^(j)(y[i]) for 0 <= j <= L[i], 1 <= i <= n, y[i] distinct, where (f/g)^(j) is the j-th derivative of the rational function f/g, f, g in K[x], GCD(f,g)=1, g <= 0, and where N = (L[1]+1)+...+(L[n]+1) >= C + D + 1 + 2(L[1]+1) + ... + 2(L[E]+1) where C is an upper bound for deg(f) and D an upper bound for deg(g), which are input to our algorithm. The arguments y[i] can be poles, which is truly or falsely indicated by a function value infinity with the corresponding L[i]=0. Our results remain valid for fields K of characteristic >= 1 + max L[i]. Our algorithm has the same asymptotic arithmetic complexity as that for classical Hermite interpolation, namely soft-O(N). For polynomials, that is, g=1, and a uniform derivative profile L[1] = ... = L[n], our algorithm specializes to the univariate multiplicity code decoder that is based on the 1986 Welch-Berlekamp algorithm.more » « less
-
Abstract In this paper, we give formulas that allow one to move between transfer function type realizations of multi-variate Schur, Herglotz, and Pick functions, without adding additional singularities except perhaps poles coming from the conformal transformation itself. In the two-variable commutative case, we use a canonical de Branges–Rovnyak model theory to obtain concrete realizations that analytically continue through the boundary for inner functions that are rational in one of the variables (so-called quasi-rational functions). We then establish a positive solution to McCarthy’s Champagne conjecture for local to global matrix monotonicity in the settings of both two-variable quasi-rational functions and $$d$$-variable perspective functions.more » « less
-
A realization is a triple, (A,b,c), consisting of a d−tuple, A=(A1,⋯,Ad), d∈N, of bounded linear operators on a separable, complex Hilbert space, H, and vectors b,c∈H. Any such realization defines an analytic non-commutative (NC) function in an open neighbourhood of the origin, 0:=(0,⋯,0), of the NC universe of d−tuples of square matrices of any fixed size. For example, a univariate realization, i.e., where A is a single bounded linear operator, defines a holomorphic function of a single complex variable, z, in an open neighbourhood of the origin via the realization formula b∗(I−zA)−1c . It is well known that an NC function has a finite-dimensional realization if and only if it is a non-commutative rational function that is defined at 0 . Such finite realizations contain valuable information about the NC rational functions they generate. By extending to infinite-dimensional realizations, we construct, study and characterize more general classes of analytic NC functions. In particular, we show that an NC function is (uniformly) entire if and only if it has a jointly compact and quasinilpotent realization. Restricting our results to one variable shows that a formal Taylor series extends globally to an entire or meromorphic function in the complex plane, C, if and only if it has a realization whose component operator is compact and quasinilpotent, or compact, respectively. This motivates our definition of the field of global (uniformly) meromorphic NC functions as the field of fractions generated by NC rational expressions in the ring of NC functions with jointly compact realizations. This definition recovers the field of meromorphic functions in C when restricted to one variable.more » « less
-
Abstract This paper solves the rational noncommutative analogue of Hilbert’s 17th problem: if a noncommutative rational function is positive semidefinite on all tuples of Hermitian matrices in its domain, then it is a sum of Hermitian squares of noncommutative rational functions. This result is a generalisation and culmination of earlier positivity certificates for noncommutative polynomials or rational functions without Hermitian singularities. More generally, a rational Positivstellensatz for free spectrahedra is given: a noncommutative rational function is positive semidefinite or undefined at every matricial solution of a linear matrix inequality $$L\succeq 0$$ if and only if it belongs to the rational quadratic module generated by L . The essential intermediate step toward this Positivstellensatz for functions with singularities is an extension theorem for invertible evaluations of linear matrix pencils.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1090/proc/16032
