Holmsen, Kynčl and Valculescu recently conjectured that if a finite set $X$ with $\ell n$ points in $\mathbb{R}^{d}$ that is colored by $m$ different colors can be partitioned into $n$ subsets of $\ell$ points each, such that each subset contains points of at least $d$ different colors, then there exists such a partition of $X$ with the additional property that the convex hulls of the $n$ subsets are pairwise disjoint. We prove a continuous analogue of this conjecture, generalized so that each subset contains points of at least $c$ different colors, where we also allow $c$ to be greater than $d$ . Furthermore, we give lower bounds on the fraction of the points each of the subsets contains from $c$ different colors. For example, when $n\geqslant 2$ , $d\geqslant 2$ , $c\geqslant d$ with $m\geqslant n(c-d)+d$ are integers, and $\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{m}$ are $m$ positive finite absolutely continuous measures on $\mathbb{R}^{d}$ , we prove that there exists a partition of $\mathbb{R}^{d}$ into $n$ convex pieces which equiparts the measures $\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{d-1}$ , and in addition every piece of the partition has positive measure with respect to at least $c$ of the measures $\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{m}$ .
more »
« less
LINEAR AND QUADRATIC UNIFORMITY OF THE MÖBIUS FUNCTION OVER
We examine correlations of the Möbius function over $\mathbb{F}_{q}[t]$ with linear or quadratic phases, that is, averages of the form 1 $$\begin{eqnarray}\frac{1}{q^{n}}\mathop{\sum }_{\deg f0$ if $Q$ is linear and $O(q^{-n^{c}})$ for some absolute constant $c>0$ if $Q$ is quadratic. The latter bound may be reduced to $O(q^{-c^{\prime }n})$ for some $c^{\prime }>0$ when $Q(f)$ is a linear form in the coefficients of $f^{2}$ , that is, a Hankel quadratic form, whereas, for general quadratic forms, it relies on a bilinear version of the additive-combinatorial Bogolyubov theorem.
more »
« less
- Award ID(s):
- 1702296
- NSF-PAR ID:
- 10106231
- Date Published:
- Journal Name:
- Mathematika
- Volume:
- 65
- Issue:
- 3
- ISSN:
- 0025-5793
- Page Range / eLocation ID:
- 505 to 529
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let $f\in C^{2}(\mathbb{T}^{2})$ have mean value 0 and consider $$\begin{eqnarray}\sup _{\unicode[STIX]{x1D6FE}\,\text{closed geodesic}}\frac{1}{|\unicode[STIX]{x1D6FE}|}\biggl|\int _{\unicode[STIX]{x1D6FE}}f\,d{\mathcal{H}}^{1}\biggr|,\end{eqnarray}$$ where $\unicode[STIX]{x1D6FE}$ ranges over all closed geodesics $\unicode[STIX]{x1D6FE}:\mathbb{S}^{1}\rightarrow \mathbb{T}^{2}$ and $|\unicode[STIX]{x1D6FE}|$ denotes its length. We prove that this supremum is always attained. Moreover, we can bound the length of the geodesic $\unicode[STIX]{x1D6FE}$ attaining the supremum in terms of the smoothness of the function: for all $s\geq 2$ , $$\begin{eqnarray}|\unicode[STIX]{x1D6FE}|^{s}{\lesssim}_{s}\biggl(\max _{|\unicode[STIX]{x1D6FC}|=s}\Vert \unicode[STIX]{x2202}_{\unicode[STIX]{x1D6FC}}f\Vert _{L^{1}(\mathbb{T}^{2})}\biggr)\Vert \unicode[STIX]{x1D6FB}f\Vert _{L^{2}}\Vert f\Vert _{L^{2}}^{-2}.\end{eqnarray}$$more » « less
-
For each $t\in \mathbb{R}$ , we define the entire function $$\begin{eqnarray}H_{t}(z):=\int _{0}^{\infty }e^{tu^{2}}\unicode[STIX]{x1D6F7}(u)\cos (zu)\,du,\end{eqnarray}$$ where $\unicode[STIX]{x1D6F7}$ is the super-exponentially decaying function $$\begin{eqnarray}\unicode[STIX]{x1D6F7}(u):=\mathop{\sum }_{n=1}^{\infty }(2\unicode[STIX]{x1D70B}^{2}n^{4}e^{9u}-3\unicode[STIX]{x1D70B}n^{2}e^{5u})\exp (-\unicode[STIX]{x1D70B}n^{2}e^{4u}).\end{eqnarray}$$ Newman showed that there exists a finite constant $\unicode[STIX]{x1D6EC}$ (the de Bruijn–Newman constant ) such that the zeros of $H_{t}$ are all real precisely when $t\geqslant \unicode[STIX]{x1D6EC}$ . The Riemann hypothesis is equivalent to the assertion $\unicode[STIX]{x1D6EC}\leqslant 0$ , and Newman conjectured the complementary bound $\unicode[STIX]{x1D6EC}\geqslant 0$ . In this paper, we establish Newman’s conjecture. The argument proceeds by assuming for contradiction that $\unicode[STIX]{x1D6EC}<0$ and then analyzing the dynamics of zeros of $H_{t}$ (building on the work of Csordas, Smith and Varga) to obtain increasingly strong control on the zeros of $H_{t}$ in the range $\unicode[STIX]{x1D6EC}null (Ed.)Abstract Let $K$ be an algebraically closed field of prime characteristic $p$ , let $X$ be a semiabelian variety defined over a finite subfield of $K$ , let $\unicode[STIX]{x1D6F7}:X\longrightarrow X$ be a regular self-map defined over $K$ , let $V\subset X$ be a subvariety defined over $K$ , and let $\unicode[STIX]{x1D6FC}\in X(K)$ . The dynamical Mordell–Lang conjecture in characteristic $p$ predicts that the set $S=\{n\in \mathbb{N}:\unicode[STIX]{x1D6F7}^{n}(\unicode[STIX]{x1D6FC})\in V\}$ is a union of finitely many arithmetic progressions, along with finitely many $p$ -sets, which are sets of the form $\{\sum _{i=1}^{m}c_{i}p^{k_{i}n_{i}}:n_{i}\in \mathbb{N}\}$ for some $m\in \mathbb{N}$ , some rational numbers $c_{i}$ and some non-negative integers $k_{i}$ . We prove that this conjecture is equivalent with some difficult diophantine problem in characteristic 0. In the case $X$ is an algebraic torus, we can prove the conjecture in two cases: either when $\dim (V)\leqslant 2$ , or when no iterate of $\unicode[STIX]{x1D6F7}$ is a group endomorphism which induces the action of a power of the Frobenius on a positive dimensional algebraic subgroup of $X$ . We end by proving that Vojta’s conjecture implies the dynamical Mordell–Lang conjecture for tori with no restriction.more » « lessmore » « less
Abstract We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in
$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ $\mathcal { C}$ $\mathcal { C}$ # SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial# SAT algorithm for a circuit class${\mathcal C}$ f (x 1,…,x n ) issparse if it outputs 1 onO (1) values of${\sum }_{i} x_{i}$ f , and for all “typical”$\mathcal { C}$ # SAT algorithms for$\mathcal { C}$ $f \circ \mathcal { C}$ stronger than$\mathcal { C}$ # SAT algorithms forn k -size$\mathcal { C}$ n /n k time (for allk ) implyN E X P does not have$(f \circ \mathcal { C})$ # SAT algorithms for$2^{n^{{\varepsilon }}}$ $\mathcal { C}$ $2^{n-n^{{\varepsilon }}}$ ε > 0) implyQ u a s i -N P does not have$(f \circ \mathcal { C})$ Applying
# SAT algorithms from the literature, one immediate corollary of our results is thatQ u a s i -N P does not haveE M A J ∘A C C 0∘T H R circuits of polynomial size, whereE M A J is the “exact majority” function, improving previous lower bounds againstA C C 0[Williams JACM’14] andA C C 0∘T H R [Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1112/S0025579319000032
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
