Let { s j } j = 1 n \left \{ s_{j}\right \} _{j=1}^{n} be positive integers. We show that for any 1 ≤ L ≤ n , 1\leq L\leq n, ‖ ∏ j = 1 n ( 1 − z s j ) ‖ L ∞ ( | z | = 1 ) ≥ exp ( 1 2 e L ( s 1 s 2 … s L ) 1 / L ) . \begin{equation*} \left \Vert \prod _{j=1}^{n}\left ( 1-z^{s_{j}}\right ) \right \Vert _{L_{\infty }\left ( \left \vert z\right \vert =1\right ) }\geq \exp \left ( \frac {1}{2e}\frac {L}{\left ( s_{1}s_{2}\ldots s_{L}\right ) ^{1/L}}\right ) . \end{equation*} In particular, this gives geometric growth if a positive proportion of the { s j } \left \{ s_{j}\right \} are bounded. We also show that when the { s j } \left \{ s_{j}\right \} grow regularly and faster than j ( log j ) 2 + ε j\left ( \log j\right ) ^{2+\varepsilon } , some ε > 0 \varepsilon >0 , then the norms grow faster than exp ( ( log n ) 1 + δ ) \exp \left ( \left ( \log n\right ) ^{1+\delta }\right ) for some δ > 0 \delta >0 .
more »
« less
Singmaster’s Conjecture In The Interior Of Pascal’s Triangle
Singmaster’s conjecture asserts that every natural number greater than one occurs at most a bounded number of times in Pascal’s triangle; that is, for any natural number $t \geq 2$, the number of solutions to the equation $\binom{n}{m} = t$ for natural numbers $1 \leq m \lt n$ is bounded. In this paper we establish this result in the interior region $\exp(\log^{2/3+\varepsilon} n) \leq m \leq n - \exp(\log^{2/3+\varepsilon} n)$ for any fixed ɛ > 0. Indeed, when t is sufficiently large depending on ɛ, we show that there are at most four solutions (or at most two in either half of Pascal’s triangle) in this region. We also establish analogous results for the equation $(n)_m = t$, where $(n)_m := n(n-1) \dots (n-m+1)$ denotes the falling factorial.
more » « less- PAR ID:
- 10371470
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- The Quarterly Journal of Mathematics
- Volume:
- 73
- Issue:
- 3
- ISSN:
- 0033-5606
- Format(s):
- Medium: X Size: p. 1137-1177
- Size(s):
- p. 1137-1177
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract The Ramsey number $r(C_{\ell },K_n)$ is the smallest natural number $N$ such that every red/blue edge colouring of a clique of order $N$ contains a red cycle of length $\ell $ or a blue clique of order $n$. In 1978, Erd̋s, Faudree, Rousseau, and Schelp conjectured that $r(C_{\ell },K_n) = (\ell -1)(n-1)+1$ for $\ell \geq n\geq 3$ provided $(\ell ,n) \neq (3,3)$. We prove that, for some absolute constant $C\ge 1$, we have $r(C_{\ell },K_n) = (\ell -1)(n-1)+1$ provided $\ell \geq C\frac{\log n}{\log \log n}$. Up to the value of $C$ this is tight since we also show that, for any $\varepsilon>0$ and $n> n_0(\varepsilon )$, we have $r(C_{\ell }, K_n) \gg (\ell -1)(n-1)+1$ for all $3 \leq \ell \leq (1-\varepsilon )\frac{\log n}{\log \log n}$. This proves the conjecture of Erd̋s, Faudree, Rousseau, and Schelp for large $\ell $, a stronger form of the conjecture due to Nikiforov, and answers (up to multiplicative constants) two further questions of Erd̋s, Faudree, Rousseau, and Schelp.
-
Let M n M_n be drawn uniformly from all ± 1 \pm 1 symmetric n × n n \times n matrices. We show that the probability that M n M_n is singular is at most exp ( − c ( n log n ) 1 / 2 ) \exp (-c(n\log n)^{1/2}) , which represents a natural barrier in recent approaches to this problem. In addition to improving on the best-known previous bound of Campos, Mattos, Morris and Morrison of exp ( − c n 1 / 2 ) \exp (-c n^{1/2}) on the singularity probability, our method is different and considerably simpler: we prove a “rough” inverse Littlewood-Offord theorem by a simple combinatorial iteration.more » « less
-
We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied problem of estimating the number of triangles in a graph stream. Our input is a k-uniform hypergraph H with n vertices and m hyperedges, each hyperedge being a k-sized subset of vertices. A k-simplex in H is a subhypergraph on k+1 vertices X such that all k+1 possible hyperedges among X exist in H. The goal is to process the hyperedges of H, which arrive in an arbitrary order as a data stream, and compute a good estimate of T_k(H), the number of k-simplices in H. We design a suite of algorithms for this problem. As with triangle-counting in graphs (which is the special case k = 2), sublinear space is achievable but only under a promise of the form T_k(H) ≥ T. Under such a promise, our algorithms use at most four passes and together imply a space bound of O(ε^{-2} log δ^{-1} polylog n ⋅ min{(m^{1+1/k})/T, m/(T^{2/(k+1)})}) for each fixed k ≥ 3, in order to guarantee an estimate within (1±ε)T_k(H) with probability ≥ 1-δ. We also give a simpler 1-pass algorithm that achieves O(ε^{-2} log δ^{-1} log n⋅ (m/T) (Δ_E + Δ_V^{1-1/k})) space, where Δ_E (respectively, Δ_V) denotes the maximum number of k-simplices that share a hyperedge (respectively, a vertex), which generalizes a previous result for the k = 2 case. We complement these algorithmic results with space lower bounds of the form Ω(ε^{-2}), Ω(m^{1+1/k}/T), Ω(m/T^{1-1/k}) and Ω(mΔ_V^{1/k}/T) for multi-pass algorithms and Ω(mΔ_E/T) for 1-pass algorithms, which show that some of the dependencies on parameters in our upper bounds are nearly tight. Our techniques extend and generalize several different ideas previously developed for triangle counting in graphs, using appropriate innovations to handle the more complicated combinatorics of hypergraphs.more » « less
-
more » « less
Abstract Given a sequence $\{Z_d\}_{d\in \mathbb{N}}$ of smooth and compact hypersurfaces in ${\mathbb{R}}^{n-1}$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$ such that each manifold $Z_d$ is diffeomorphic to a component of the zero set on $\Gamma$ of some polynomial of degree $d$. (This is in sharp contrast with the case when $\Gamma$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $p$ on $\Gamma$ is bounded by a polynomial in $\deg (p)$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$ containing a subset $D$ homeomorphic to a disk, and a family of polynomials $\{p_m\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that $(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$ i.e. the zero set of $p_m$ in $D$ is isotopic to $Z_{d_m}$ in ${\mathbb{R}}^{n-1}$. This says that, up to extracting subsequences, the intersection of $\Gamma$ with a hypersurface of degree $d$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $0 \leq k \leq n-2$ and every sequence of natural numbers $a=\{a_d\}_{d\in \mathbb{N}}$ there is a regular, compact semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$, a subsequence $\{a_{d_m}\}_{m\in \mathbb{N}}$ and homogeneous polynomials $\{p_{m}\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $b_k$ denotes the $k$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $\Gamma$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $d$, of the set $\Sigma _{d_m,a, \Gamma }$ of polynomials verifying (0.1) is positive, but there exists a constant $c_\Gamma$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n-1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $a$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $\Gamma$, for most polynomials a Bézout-type bound holds for the intersection $\Gamma \cap Z(p)$: for every $0\leq k\leq n-2$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n-1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n-1}{2}}}.\end{equation*}$$
