More Like this

1. Poisson Approximation of Prime Divisors of Shifted Primes

   https://doi.org/10.1093/imrn/rnaf079  

   Ford, Kevin (April 2025, International Mathematics Research Notices)

   Abstract We develop an analog for shifted primes of the Kubilius model of prime factors of integers. We prove a total variation distance estimate for the difference between the model and actual prime factors of shifted primes, and apply it to show that the prime factors of shifted primes in disjoint sets behave like independent Poisson variables. As a consequence, we establish a transference principle between the anatomy of random integers $$\leqslant x$$ and of random shifted primes p+a with $$p\leqslant x$$. 

   more » « less
2. ROUGH INTEGERS WITH A DIVISOR IN A GIVEN INTERVAL

   https://doi.org/10.1017/S1446788719000442  

   FORD, KEVIN (August 2021, Journal of the Australian Mathematical Society)

   Abstract We determine, up to multiplicative constants, the number of integers $$n\leq x$$ that have a divisor in $(y,2y]$ and no prime factor $$\leq w$$ . Our estimate is uniform in $x,y,w$ . We apply this to determine the order of the number of distinct integers in the $$N\times N$$ multiplication table, which are free of prime factors $$\leq w$$ , and the number of distinct fractions of the form $$(a_{1}a_{2})/(b_{1}b_{2})$$ with $$1\leq a_{1}\leq b_{1}\leq N$$ and $$1\leq a_{2}\leq b_{2}\leq N$$ . 

   more » « less
3. Reduction of dynatomic curves

   https://doi.org/10.1017/etds.2017.140  

   DOYLE, JOHN R.; KRIEGER, HOLLY; OBUS, ANDREW; PRIES, RACHEL; RUBINSTEIN-SALZEDO, SIMON; WEST, LLOYD (October 2019, Ergodic Theory and Dynamical Systems)

   null (Ed.)

   In this paper, we make partial progress on a function field version of the dynamical uniform boundedness conjecture for certain one-dimensional families $${\mathcal{F}}$$ of polynomial maps, such as the family $$f_{c}(x)=x^{m}+c$$ , where $$m\geq 2$$ . We do this by making use of the dynatomic modular curves $$Y_{1}(n)$$ (respectively $$Y_{0}(n)$$ ) which parametrize maps $$f$$ in $${\mathcal{F}}$$ together with a point (respectively orbit) of period $$n$$ for $$f$$ . The key point in our strategy is to study the set of primes $$p$$ for which the reduction of $$Y_{1}(n)$$ modulo $$p$$ fails to be smooth or irreducible. Morton gave an algorithm to construct, for each $$n$$ , a discriminant $$D_{n}$$ whose list of prime factors contains all the primes of bad reduction for $$Y_{1}(n)$$ . In this paper, we refine and strengthen Morton’s results. Specifically, we exhibit two criteria on a prime $$p$$ dividing $$D_{n}$$ : one guarantees that $$p$$ is in fact a prime of bad reduction for $$Y_{1}(n)$$ , yet this same criterion implies that $$Y_{0}(n)$$ is geometrically irreducible. The other guarantees that the reduction of $$Y_{1}(n)$$ modulo $$p$$ is actually smooth. As an application of the second criterion, we extend results of Morton, Flynn, Poonen, Schaefer, and Stoll by giving new examples of good reduction of $$Y_{1}(n)$$ for several primes dividing $$D_{n}$$ when $n=7,8,11$ , and $$f_{c}(x)=x^{2}+c$$ . The proofs involve a blend of arithmetic and complex dynamics, reduction theory for curves, ramification theory, and the combinatorics of the Mandelbrot set. 

   more » « less
4. Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.11  

   Chlamtáč, Eden; Makarychev, Yury; Vakilian, Ali (September 2023, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023))

   Megow, Nicole; Smith, Adam (Ed.)

   We provide new approximation algorithms for the Red-Blue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for Red-Blue Set Cover achieves Õ(m^{1/3})-approximation improving on the Õ(m^{1/2})-approximation due to Elkin and Peleg (where m is the number of sets). Our approximation algorithm for MMSA_t (for circuits of depth t) gives an Õ(N^{1-δ}) approximation for δ = 1/3 2^{3-⌈t/2⌉}, where N is the number of gates and variables. No non-trivial approximation algorithms for MMSA_t with t ≥ 4 were previously known. We complement these results with lower bounds for these problems: For Red-Blue Set Cover, we provide a nearly approximation preserving reduction from Min k-Union that gives an Ω(m^{1/4 - ε}) hardness under the Dense-vs-Random conjecture, while for MMSA we sketch a proof that an SDP relaxation strengthened by Sherali-Adams has an integrality gap of N^{1-ε} where ε → 0 as the circuit depth t → ∞. 

   more » « less
5. A nearly-optimal bound for fast regression with ℓ∞ guarantee

   Song, Zhao; Ye, Mingquan; Yin, Junze; Zhang, Lichen (July 2023, Proceedings of Machine Learning Research)

   Given a matrix A ∈ ℝn\texttimes{}d and a vector b ∈ ℝn, we consider the regression problem with ℓ∞ guarantees: finding a vector x′ ∈ ℝd such that $$||x'-x^* ||_infty leq frac{epsilon}{sqrt{d}}cdot ||Ax^*-b||_2cdot ||A^dagger||$$, where x* = arg minx∈Rd ||Ax – b||2. One popular approach for solving such ℓ2 regression problem is via sketching: picking a structured random matrix S ∈ ℝm\texttimes{}n with m < n and S A can be quickly computed, solve the "sketched" regression problem arg minx∈ℝd ||S Ax – Sb||2. In this paper, we show that in order to obtain such ℓ∞ guarantee for ℓ2 regression, one has to use sketching matrices that are dense. To the best of our knowledge, this is the first user case in which dense sketching matrices are necessary. On the algorithmic side, we prove that there exists a distribution of dense sketching matrices with m = ε-2d log3(n/δ) such that solving the sketched regression problem gives the ℓ∞ guarantee, with probability at least 1 – δ. Moreover, the matrix S A can be computed in time O(nd log n). Our row count is nearly-optimal up to logarithmic factors, and significantly improves the result in (Price et al., 2017), in which a superlinear in d rows, m = Ω(ε-2d1+γ) for γ ∈ (0, 1) is required. Moreover, we develop a novel analytical framework for ℓ∞ guarantee regression that utilizes the Oblivious Coordinate-wise Embedding (OCE) property introduced in (Song \& Yu, 2021). Our analysis is much simpler and more general than that of (Price et al., 2017). Leveraging this framework, we extend the ℓ∞ guarantee regression result to dense sketching matrices for computing the fast tensor product of vectors. 

   more » « less