skip to main content

Title: Joint Poisson distribution of prime factors in sets
Abstarct Given disjoint subsets T 1 , …, T m of “not too large” primes up to x , we establish that for a random integer n drawn from [1, x ], the m -dimensional vector enumerating the number of prime factors of n from T 1 , …, T m converges to a vector of m independent Poisson random variables. We give a specific rate of convergence using the Kubilius model of prime factors. We also show a universal upper bound of Poisson type when T 1 , …, T m are unrestricted, and apply this to the distribution of the number of prime factors from a set T conditional on n having k total prime factors.  more » « less
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
Mathematical Proceedings of the Cambridge Philosophical Society
Page Range / eLocation ID:
189 to 200
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. MCMC chains for the GWB analyses performed in the paper "The NANOGrav 15 yr Data Set: Search for Signals from New Physics". 

    The data is provided in pickle format. Each file contains a NumPy array with the MCMC chain (with burn-in already removed), and a dictionary with the model parameters' names as keys and their priors as values. You can load them as

    with open ('path/to/file.pkl', 'rb') as pick: temp = pickle.load(pick) params = temp[0] chain = temp[1]

    The naming convention for the files is the following:

    • igw: inflationary Gravitational Waves (GWs)
    • sigw: scalar-induced GWs
      • sigw_box: assumes a box-like feature in the primordial power spectrum.
      • sigw_delta: assumes a delta-like feature in the primordial power spectrum.
      • sigw_gauss: assumes a Gaussian peak feature in the primordial power spectrum.
    • pt: cosmological phase transitions
      • pt_bubble: assumes that the dominant contribution to the GW productions comes from bubble collisions.
      • pt_sound: assumes that the dominant contribution to the GW productions comes from sound waves.
    • stable: stable cosmic strings
      • stable-c: stable strings emitting GWs only in the form of GW bursts from cusps on closed loops.
      • stable-k: stable strings emitting GWs only in the form of GW bursts from kinks on closed loops.
      • stable-m: stable strings emitting monochromatic GW at the fundamental frequency.
      • stable-n: stable strings described by numerical simulations including GWs from cusps and kinks.
    • meta: metastable cosmic strings
      • meta-l: metastable strings with GW emission from loops only.
      • meta-ls metastable strings with GW emission from loops and segments.
    • super: cosmic superstrings.
    • dw: domain walls
      • dw-sm: domain walls decaying into Standard Model particles.
      • dw-dr: domain walls decaying into dark radiation.

    For each model, we provide four files. One for the run where the new-physics signal is assumed to be the only GWB source. One for the run where the new-physics signal is superimposed to the signal from Supermassive Black Hole Binaries (SMBHB), for these files "_bhb" will be appended to the model name. Then, for both these scenarios, in the "compare" folder we provide the files for the hypermodel runs that were used to derive the Bayes' factors.

    In addition to chains for the stochastic models, we also provide data for the two deterministic models considered in the paper (ULDM and DM substructures). For the ULDM model, the naming convention of the files is the following (all the ULDM signals are superimposed to the SMBHB signal, see the discussion in the paper for more details)

    • uldm_e: ULDM Earth signal.
    • uldm_p: ULDM pulsar signal
      • uldm_p_cor: correlated limit
      • uldm_p_unc: uncorrelated limit
    • uldm_c: ULDM combined Earth + pulsar signal direct coupling 
      • uldm_c_cor: correlated limit
      • uldm_c_unc: uncorrelated limit
    • uldm_vecB: vector ULDM coupled to the baryon number
      • uldm_vecB_cor: correlated limit
      • uldm_vecB_unc: uncorrelated limit 
    • uldm_vecBL: vector ULDM coupled to B-L
      • uldm_vecBL_cor: correlated limit
      • uldm_vecBL_unc: uncorrelated limit
    • uldm_c_grav: ULDM combined Earth + pulsar signal for gravitational-only coupling
      • uldm_c_grav_cor: correlated limit
        • uldm_c_cor_grav_low: low mass region  
        • uldm_c_cor_grav_mon: monopole region
        • uldm_c_cor_grav_low: high mass region
      • uldm_c_unc: uncorrelated limit
        • uldm_c_unc_grav_low: low mass region  
        • uldm_c_unc_grav_mon: monopole region
        • uldm_c_unc_grav_low: high mass region

    For the substructure (static) model, we provide the chain for the marginalized distribution (as for the ULDM signal, the substructure signal is always superimposed to the SMBHB signal)

    more » « less
  2. Abstract This paper is concerned with the phase estimation algorithm in quantum computing, especially the scenarios where (1) the input vector is not an eigenvector; (2) the unitary operator is approximated by Trotter or Taylor expansion methods; (3) random approximations are used for the unitary operator. We characterize the probability of computing the phase values in terms of the consistency error, including the residual error, Trotter splitting error, or statistical mean-square error. In the first two cases, we show that in order to obtain the phase value with error less or equal to 2 − n and probability at least 1 − ϵ , the required number of qubits is t ⩾ n + log 2 + δ 2 2 ϵ Δ E 2 . The parameter δ quantifies the error associated with the inexact eigenvector and/or the unitary operator, and Δ E characterizes the spectral gap, i.e., the separation from the rest of the phase values. This analysis generalizes the standard result (Cleve et al 1998 Phys. Rev X 11 011020; Nielsen and Chuang 2002 Quantum Computation and Quantum Information ) by including these effects. More importantly, it shows that when δ < Δ E , the complexity remains the same. For the third case, we found a similar estimate, but the number of random steps has to be sufficiently large. 
    more » « less
  3. Lysyanskaya, Anna ; Handschuh, Helena (Ed.)
    We study the black-box function inversion problem, which is the problem of finding x[N] such that f(x)=y, given as input some challenge point y in the image of a function f:[N][N], using T oracle queries to f and preprocessed advice 01S depending on f. We prove a number of new results about this problem, as follows. 1. We show an algorithm that works for any T and S satisfying TS2maxST=(N3) . In the important setting when ST, this improves on the celebrated algorithm of Fiat and Naor [STOC, 1991], which requires TS3N3. E.g., Fiat and Naor's algorithm is only non-trivial for SN23 , while our algorithm gives a non-trivial tradeoff for any SN12 . (Our algorithm and analysis are quite simple. As a consequence of this, we also give a self-contained and simple proof of Fiat and Naor's original result, with certain optimizations left out for simplicity.) 2. We show a non-adaptive algorithm (i.e., an algorithm whose ith query xi is chosen based entirely on and y, and not on the f(x1)f(xi−1)) that works for any T and S satisfying S=(Nlog(NT)) giving the first non-trivial non-adaptive algorithm for this problem. E.g., setting T=Npolylog(N) gives S=(NloglogN). This answers a question due to Corrigan-Gibbs and Kogan [TCC, 2019], who asked whether it was possible for a non-adaptive algorithm to work with parameters T and S satisfying T+SlogNo(N) . We also observe that our non-adaptive algorithm is what we call a guess-and-check algorithm, that is, it is non-adaptive and its final output is always one of the oracle queries x1xT. For guess-and-check algorithms, we prove a matching lower bound, therefore completely characterizing the achievable parameters (ST) for this natural class of algorithms. (Corrigan-Gibbs and Kogan showed that any such lower bound for arbitrary non-adaptive algorithms would imply new circuit lower bounds.) 3. We show equivalence between function inversion and a natural decision version of the problem in both the worst case and the average case, and similarly for functions f:[N][M] with different ranges. All of the above results are most naturally described in a model with shared randomness (i.e., random coins shared between the preprocessing algorithm and the online algorithm). However, as an additional contribution, we show (using a technique from communication complexity due to Newman [IPL, 1991]) how to generically convert any algorithm that uses shared randomness into one that does not. 
    more » « less
  4. Abstract

    We investigate the asymptotics of the total number of simple $(4a+1)$-knots with Alexander polynomial of the form $mt^2 +(1-2m) t + m$ for some nonzero $m \in [-X, X]$. Using Kearton and Levine’s classification of simple knots, we give equivalent algebraic and arithmetic formulations of this counting question. In particular, this count is the same as the total number of ${\mathbb{Z}}[1/m]$-equivalence classes of binary quadratic forms of discriminant $1-4m$, for $m$ running through the same range. Our heuristics, based on the Cohen–Lenstra heuristics, suggest that this total is asymptotic to $X^{3/2}/\log X$ and the largest contribution comes from the values of $m$ that are positive primes. Using sieve methods, we prove that the contribution to the total coming from $m$ positive prime is bounded above by $O(X^{3/2}/\log X)$ and that the total itself is $o(X^{3/2})$.

    more » « less
  5. Dozois, Charles M. (Ed.)
    ABSTRACT Vibrio spp. and phytoplankton are naturally abundant in marine environments. Recent studies have suggested that the co-occurrence of phytoplankton and the pathogenic bacterium Vibrio parahaemolyticus is due to shared ecological factors, such as nutrient requirements. We compared these communities at two locations in the Delaware Inland Bays, representing a site with high anthropogenic inputs (Torquay Canal) and a less developed area (Sloan Cove). In 2017 to 2018, using light microscopy, we were able to identify the presence of many bloom-forming algal species, such as Karlodinium veneficum , Dinophysis acuminata , Heterosigma akashiwo , and Chattonella subsalsa . Dinoflagellate biomass was higher at Torquay Canal than that at Sloan Cove. D. acuminata and Chloromorum toxicum were found only at Torquay Canal and were not observed in Sloan Cove. Most probable number real-time PCR revealed V. parahaemolyticus and Vibrio vulnificus in environmental samples. The abundance of vibrios and their virulence genes varied between sites, with a significant association between total dissolved nitrogen (TDN), PO 4 − , total dissolved phosphorus (TDP), and pathogenic markers. A generalized linear model revealed that principal component 1 of environmental factors (temperature, dissolved oxygen, salinity, TDN, PO 4 − , TDP, NO 3 :NO 2 , NO 2 − , and NH 4 + ) was the best at detecting total ( tlh+ ) V. parahaemolyticus , suggesting that they are the prime drivers for the growth and distribution of pathogenic Vibrio spp. IMPORTANCE Vibrio-associated illnesses have been expanding globally over the past several decades (A. Newton, M. Kendall, D. J. Vugia, O. L. Henao, and B. E. Mahon, Clin Infect Dis 54:S391–S395, 2012, ). Many studies have linked this expansion with an increase in global temperature (J. Martinez-Urtaza, B. C. John, J. Trinanes, and A. DePaola, Food Res Int 43:10, 2010, ; L. Vezzulli, R. R. Colwell, and C. Pruzzo, Microb Ecol 65:817–825, 2013, ; R. N. Paranjpye, W. B. Nilsson, M. Liermann, and E. D. Hilborn, FEMS Microbiol Ecol 91:fiv121, 2015, ). Temperature and salinity are the two major factors affecting the distribution of Vibrio spp. (D. Ceccarelli and R. R. Colwell, Front Microbiol 5:256, 2014, ). However, Vibrio sp. abundance can also be affected by nutrient load and marine plankton blooms (V. J. McKenzie and A. R. Townsend, EcoHealth 4:384–396, 2007; L. Vezzulli, C. Pruzzo, A. Huq, and R. R. Colwell, Environ Microbiol Rep 2:27–33, 2010, ; S. Liu, Z. Jiang, Y. Deng, Y. Wu, J. Zhang, et al. Microbiologyopen 7:e00600, 2018, ). The expansion of Vibrio spp. in marine environments calls for a deeper understanding of the biotic and abiotic factors that play a role in their abundance. We observed that pathogenic Vibrio spp. were most abundant in areas that favor the proliferation of harmful algal bloom (HAB) species. These results can inform managers, researchers, and oyster growers on factors that can influence the growth and distribution of pathogenic Vibrio spp. in the Delaware Inland Bays. 
    more » « less