An official website of the United States government
Abstract We study the extent to which divisors of a typical integer n are concentrated. In particular, defining $$\Delta (n) := \max _t \# \{d | n, \log d \in [t,t+1]\}$$ Δ ( n ) : = max t # { d | n , log d ∈ [ t , t + 1 ] } , we show that $$\Delta (n) \geqslant (\log \log n)^{0.35332277\ldots }$$ Δ ( n ) ⩾ ( log log n ) 0.35332277 … for almost all n , a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for the concentration of divisors of a random permutation and of a random polynomial over a finite field. Most of the paper is devoted to a study of the following much more combinatorial problem of independent interest. Pick a random set $${\textbf{A}} \subset {\mathbb {N}}$$ A ⊂ N by selecting i to lie in $${\textbf{A}}$$ A with probability 1/ i . What is the supremum of all exponents $$\beta _k$$ β k such that, almost surely as $$D \rightarrow \infty $$ D → ∞ , some integer is the sum of elements of $${\textbf{A}} \cap [D^{\beta _k}, D]$$ A ∩ [ D β k , D ] in k different ways? We characterise $$\beta _k$$ β k as the solution to a certain optimisation problem over measures on the discrete cube $$\{0,1\}^k$$ { 0 , 1 } k , and obtain lower bounds for $$\beta _k$$ β k which we believe to be asymptotically sharp.
more »
« less
A blurred view of Van der Waerden type theorems
Abstract Let $$\mathrm{AP}_k=\{a,a+d,\ldots,a+(k-1)d\}$$ be an arithmetic progression. For $$\varepsilon>0$$ we call a set $$\mathrm{AP}_k(\varepsilon)=\{x_0,\ldots,x_{k-1}\}$$ an $$\varepsilon$$ -approximate arithmetic progression if for some a and d , $$|x_i-(a+id)|<\varepsilon d$$ holds for all $$i\in\{0,1\ldots,k-1\}$$ . Complementing earlier results of Dumitrescu (2011, J. Comput. Geom. 2 (1) 16–29), in this paper we study numerical aspects of Van der Waerden, Szemerédi and Furstenberg–Katznelson like results in which arithmetic progressions and their higher dimensional extensions are replaced by their $$\varepsilon$$ -approximation.
more »
« less
- Award ID(s):
- 1764385
- PAR ID:
- 10316754
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- ISSN:
- 0963-5483
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract We show how to construct a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner over a set $${P}$$ P of n points in $${\mathbb {R}}^d$$ R d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $${\vartheta },\varepsilon \in (0,1)$$ ϑ , ε ∈ ( 0 , 1 ) , the computed spanner $${G}$$ G has $$\begin{aligned} {{\mathcal {O}}}\bigl (\varepsilon ^{-O(d)} {\vartheta }^{-6} n(\log \log n)^6 \log n \bigr ) \end{aligned}$$ O ( ε - O ( d ) ϑ - 6 n ( log log n ) 6 log n ) edges. Furthermore, for any k , and any deleted set $${{B}}\subseteq {P}$$ B ⊆ P of k points, the residual graph $${G}\setminus {{B}}$$ G \ B is a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner for all the points of $${P}$$ P except for $$(1+{\vartheta })k$$ ( 1 + ϑ ) k of them. No previous constructions, beyond the trivial clique with $${{\mathcal {O}}}(n^2)$$ O ( n 2 ) edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices, $$\vartheta |B|$$ ϑ | B | , lose their distance preserving connectivity). Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black-box fashion.more » « less
-
null (Ed.)A bstract The p T -differential production cross sections of prompt and non-prompt (produced in beauty-hadron decays) D mesons were measured by the ALICE experiment at midrapidity ( | y | < 0 . 5) in proton-proton collisions at $$ \sqrt{s} $$ s = 5 . 02 TeV. The data sample used in the analysis corresponds to an integrated luminosity of (19 . 3 ± 0 . 4) nb − 1 . D mesons were reconstructed from their decays D 0 → K − π + , D + → K − π + π + , and $$ {\mathrm{D}}_{\mathrm{s}}^{+}\to \upphi {\uppi}^{+}\to {\mathrm{K}}^{-}{\mathrm{K}}^{+}{\uppi}^{+} $$ D s + → ϕ π + → K − K + π + and their charge conjugates. Compared to previous measurements in the same rapidity region, the cross sections of prompt D + and $$ {\mathrm{D}}_{\mathrm{s}}^{+} $$ D s + mesons have an extended p T coverage and total uncertainties reduced by a factor ranging from 1.05 to 1.6, depending on p T , allowing for a more precise determination of their p T -integrated cross sections. The results are well described by perturbative QCD calculations. The fragmentation fraction of heavy quarks to strange mesons divided by the one to non-strange mesons, f s / ( f u + f d ), is compatible for charm and beauty quarks and with previous measurements at different centre-of-mass energies and collision systems. The $$ \mathrm{b}\overline{\mathrm{b}} $$ b b ¯ production cross section per rapidity unit at midrapidity, estimated from non-prompt D-meson measurements, is $$ \mathrm{d}{\sigma}_{\mathrm{b}\overline{\mathrm{b}}}/\mathrm{d}y\left|{}_{\left|\mathrm{y}\right|<0.5}=34.5\pm 2.4{\left(\mathrm{stat}\right)}_{-2.9}^{+4.7}\left(\mathrm{tot}.\mathrm{syst}\right)\right. $$ d σ b b ¯ / d y y < 0.5 = 34.5 ± 2.4 stat − 2.9 + 4.7 tot . syst μb. It is compatible with previous measurements at the same centre-of-mass energy and with the cross section pre- dicted by perturbative QCD calculations.more » « less
-
Abstract A bipartite graph $$H = \left (V_1, V_2; E \right )$$ with $$\lvert V_1\rvert + \lvert V_2\rvert = n$$ is semilinear if $$V_i \subseteq \mathbb {R}^{d_i}$$ for some $$d_i$$ and the edge relation E consists of the pairs of points $$(x_1, x_2) \in V_1 \times V_2$$ satisfying a fixed Boolean combination of s linear equalities and inequalities in $$d_1 + d_2$$ variables for some s . We show that for a fixed k , the number of edges in a $$K_{k,k}$$ -free semilinear H is almost linear in n , namely $$\lvert E\rvert = O_{s,k,\varepsilon }\left (n^{1+\varepsilon }\right )$$ for any $$\varepsilon> 0$$ ; and more generally, $$\lvert E\rvert = O_{s,k,r,\varepsilon }\left (n^{r-1 + \varepsilon }\right )$$ for a $$K_{k, \dotsc ,k}$$ -free semilinear r -partite r -uniform hypergraph. As an application, we obtain the following incidence bound: given $$n_1$$ points and $$n_2$$ open boxes with axis-parallel sides in $$\mathbb {R}^d$$ such that their incidence graph is $$K_{k,k}$$ -free, there can be at most $$O_{k,\varepsilon }\left (n^{1+\varepsilon }\right )$$ incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of half-spaces. We also obtain matching upper and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the model-theoretic trichotomy in o -minimal structures (showing that the failure of an almost-linear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).more » « less
-
Abstract The Euler–Mascheroni constant $$\gamma =0.5772\ldots \!$$ is the $$K={\mathbb Q}$$ example of an Euler–Kronecker constant $$\gamma _K$$ of a number field $K.$ In this note, we consider the size of the $$\gamma _q=\gamma _{K_q}$$ for cyclotomic fields $$K_q:={\mathbb Q}(\zeta _q).$$ Assuming the Elliott–Halberstam Conjecture (EH), we prove uniformly in Q that $$ \begin{align*} \frac{1}{Q}\sum_{Qmore » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/S0963548321000535
