Abstract For the partition functionp(n), Ramanujan proved the striking identities$$\begin{aligned} \begin{aligned} \mathcal {P}_5(q):=\sum _{n\ge 0} p(5n+4)q^n&=5\prod _{n\ge 1} \frac{\left( q^5;q^5\right) _{\infty }^5}{(q;q)_{\infty }^6},\\ \mathcal {P}_{7}(q):=\sum _{n\ge 0} p(7n+5)q^n&=7\prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^3}{(q;q)_{\infty }^4}+49q \prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^7}{(q;q)_{\infty }^8}, \end{aligned} \end{aligned}$$ where$$(q;q)_{\infty }:=\prod _{n\ge 1}(1-q^n).$$ As these identities imply his celebrated congruences modulo 5 and 7, it is natural to seek, for primes$$\ell \ge 5,$$ closed form expressions of the power series$$ \mathcal {P}_{\ell }(q):=\sum _{n\ge 0} p(\ell n-\delta _{\ell })q^n\pmod {\ell }, $$ where$$\delta _{\ell }:=\frac{\ell ^2-1}{24}.$$ In this paper, we prove that$$ \mathcal {P}_{\ell }(q)\equiv c_{\ell } \dfrac{\mathcal {T}_{\ell }(q)}{\left( q^\ell ; q^\ell \right) _\infty } \pmod {\ell }, $$ where$$c_{\ell }\in \mathbb Z$$ is explicit and$${\mathcal {T}}_{\ell }(q)$$ is the generating function for the Hecke traces of$$\ell $$ -ramified values of special Dirichlet series for weight$$\ell -1$$ cusp forms on$$\textrm{SL}_2(\mathbb Z)$$ . This is a new proof of Ramanujan’s congruences modulo 5, 7, and 11, as there are no nontrivial cusp forms of weight 4, 6, and 10.
more »
« less
Hardness and approximation of submodular minimum linear ordering problems
Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ due to an ordering$$\sigma $$ of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ , where$$E_{i,\sigma }$$ is the set of items mapped by$$\sigma $$ to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ -approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ satisfies$$1 \le \ell _f \le |E|$$ . Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ -approximation for the matroid MLOP, where$$f = r$$ is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ -approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.
more »
« less
- Award ID(s):
- 2151283
- PAR ID:
- 10525122
- Publisher / Repository:
- Springer Verlag
- Date Published:
- Journal Name:
- Mathematical Programming
- ISSN:
- 0025-5610
- Subject(s) / Keyword(s):
- Submodular optimization graph labeling approximation algorithm linear arrangement
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let$$\mathbb {F}_q^d$$ be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ and a fixed nonzero$$t\in \mathbb {F}_q$$ , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ , where$$h_y:E\rightarrow \{0,1\}$$ is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ . Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ that if$$|E|\ge Cq^{\frac{11}{4}}$$ andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ isdwhenever$$E\subseteq \mathbb {F}_q^d$$ with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ .more » « less
-
Abstract We study holomorphic mapsFfrom a smooth Levi non-degenerate real hypersurface$$ M_{\ell }\subset {\mathbb {C}}^n $$ into a hyperquadric$$ {\mathbb {H}}_{\ell '}^N $$ with signatures$$ \ell \le (n-1)/2 $$ and$$ \ell '\le (N-1)/2,$$ respectively. Assuming that$$ N - n < n - 1,$$ we prove that if$$ \ell = \ell ',$$ thenFis either CR transversal to$$ {\mathbb {H}}_{\ell }^N $$ at every point of$$ M_{\ell },$$ or it maps a neighborhood of$$ M_{\ell } $$ in$$ {\mathbb {C}}^n $$ into$$ {\mathbb {H}}_{\ell }^N.$$ Furthermore, in the case where$$ \ell ' > \ell ,$$ we show that ifFis not CR transversal at$$0\in M_\ell ,$$ then it must be transversally flat. The latter is best possible.more » « less
-
Abstract LetXbe a compact normal complex space of dimensionnandLbe a holomorphic line bundle onX. Suppose that$$\Sigma =(\Sigma _1,\ldots ,\Sigma _\ell )$$ is an$$\ell $$ -tuple of distinct irreducible proper analytic subsets ofX,$$\tau =(\tau _1,\ldots ,\tau _\ell )$$ is an$$\ell $$ -tuple of positive real numbers, and let$$H^0_0(X,L^p)$$ be the space of holomorphic sections of$$L^p:=L^{\otimes p}$$ that vanish to order at least$$\tau _jp$$ along$$\Sigma _j$$ ,$$1\le j\le \ell $$ . If$$Y\subset X$$ is an irreducible analytic subset of dimensionm, we consider the space$$H^0_0 (X|Y, L^p)$$ of holomorphic sections of$$L^p|_Y$$ that extend to global holomorphic sections in$$H^0_0(X,L^p)$$ . Assuming that the triplet$$(L,\Sigma ,\tau )$$ is big in the sense that$$\dim H^0_0(X,L^p)\sim p^n$$ , we give a general condition onYto ensure that$$\dim H^0_0(X|Y,L^p)\sim p^m$$ . WhenLis endowed with a continuous Hermitian metric, we show that the Fubini-Study currents of the spaces$$H^0_0(X|Y,L^p)$$ converge to a certain equilibrium current onY. We apply this to the study of the equidistribution of zeros inYof random holomorphic sections in$$H^0_0(X|Y,L^p)$$ as$$p\rightarrow \infty $$ .more » « less
-
Abstract A family ofrdistinct sets$$\{A_1,\ldots , A_r\}$$ is anr-sunflower if for all$$1 \leqslant i < j\leqslant r$$ and$$1 \leqslant i' < j'\leqslant r$$ , we have$$A_i\cap A_j = A_{i'}\cap A_{j'}$$ . Erdős and Rado conjectured in 1960 that every family$$\mathcal {H}$$ of$$\ell $$ -element sets of size at least$$K(r)^\ell $$ contains anr-sunflower, whereK(r) is some function that depends only onr. We prove that if$$\mathcal {H}$$ is a family of$$\ell $$ -element sets of VC-dimension at mostdand$$|\mathcal H| > (C r(\log d+\log ^*\ell ))^\ell $$ for some absolute constant$$C > 0$$ , then$$\mathcal {H}$$ contains anr-sunflower. This improves a recent result of Fox, Pach, and Suk. When$$d=1$$ , we obtain a sharp bound, namely that$$|\mathcal H| > (r-1)^\ell $$ is sufficient. Along the way, we establish a strengthening of the Kahn–Kalai conjecture for set families of bounded VC-dimension, which is of independent interest.more » « less
An official website of the United States government

