Skip to main content
added 1 character in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

Below I explain how one treats the case where $y$ grows sufficiently fast with $x$ (namely, $y \ge (\log x)^{1+1/(k-1)+\varepsilon}$), but I'll start with a general discussion.

First of all, in this case it is often useful to introduce a truncation parameter $T>0$ into the above inclusion-exclusion formula, and obtain via the union bound the estimate $$ (\star)\, S_k(x, y) = \sum_{d \text{ is }T\text{-smooth}} \mu(d) \Psi(x/d,y)^k + O\left( \sum_{y\ge p > T} \Psi(x/p,y)^k \right).$$ The ratio $\Psi(x/d,y)/\Psi(x,y)$ (`local'local density') was studied extensively in the literature, namely in

Below I explain how one treats the case where $y$ grows sufficiently fast with $x$ (namely, $y \ge (\log x)^{1+1/(k-1)+\varepsilon}$, but I'll start with a general discussion.

First of all, in this case it is often useful to introduce a truncation parameter $T>0$ into the above inclusion-exclusion formula, and obtain via the union bound the estimate $$ (\star)\, S_k(x, y) = \sum_{d \text{ is }T\text{-smooth}} \mu(d) \Psi(x/d,y)^k + O\left( \sum_{y\ge p > T} \Psi(x/p,y)^k \right).$$ The ratio $\Psi(x/d,y)/\Psi(x,y)$ (`local density') was studied extensively in the literature, namely in

Below I explain how one treats the case where $y$ grows sufficiently fast with $x$ (namely, $y \ge (\log x)^{1+1/(k-1)+\varepsilon}$), but I'll start with a general discussion.

First of all, in this case it is often useful to introduce a truncation parameter $T>0$ into the above inclusion-exclusion formula, and obtain via the union bound the estimate $$ (\star)\, S_k(x, y) = \sum_{d \text{ is }T\text{-smooth}} \mu(d) \Psi(x/d,y)^k + O\left( \sum_{y\ge p > T} \Psi(x/p,y)^k \right).$$ The ratio $\Psi(x/d,y)/\Psi(x,y)$ ('local density') was studied extensively in the literature, namely in

deleted 5 characters in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

Let me formalize the problem and explain some some results.

Let me formalize the problem and explain some some results.

Let me formalize the problem and explain some results.

Found a reference where this exact problem is discussed.
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

This question, at least for $k=2$, was studied by Gunderson, Coppersmith and Granville. Surprisingly, the motivation has to do with the first case of Fermat's Last Theorem, but I won't elaborate on that. See specifically Granville's paper "On positive integers $\le x$ with prime factors $\le t \log x$" (Number Theory and Applications (ed R.A. Mollin) (Kluwer, NATO ASI, 1989), pages 403-422, PDF link).

Let me formalize the problem and giveexplain some some results. iv A

A number $n$ is $y$-smooth (or $y$-friable) if all its prime factors $p$ are less than or equal to $y$. Let us set $$\Psi(x,y) :=\# \{ n \le x: n \text{ is }y\text{-smooth}\},$$ which appeared in Sungjin Kim's comment. One can consider the quantity $$S_k(x,y) := \# \{ n_1,\ldots,n_k \le x: \gcd(n_1,n_2,\ldots,n_k)=1, \, n_i \text{ is }y\text{-smooth}\}.$$ The ratio $S_k(x,y)/\Psi(x,y)^k$ is exactly the probability that $n$ positive integers chosen uniformly at random from the set of $y$-smooth numbers up to $x$ have no non-trivial common factor. Equivalently, it is the probability that a vector of $y$-smooth numbers and $L^1$-norm $\le x$ is visible from the origin.

Below I discuss what happens ifIn Granville's paper linked above, he studies the quantity $\Psi(x,x',y)$, which counts pairs $(a,b)$ of coprime $y$-smooth integers with $a \le x$ and $b\le x'$. For $x'=x$, $\Psi(x,x,y)$ is allowedprecisely $S_2(x,y)$. In pages 8--9 he quickly derives the following results, and the arguments should extend to grow$S_k(x,y)$:

  • For $2 \le y \le (\log x)^{1/2}$, we have $\Psi(x,x,y) \sim \binom{2\pi(y)}{\pi(y)} \Psi(x,y)$ as $x \to \infty$. Note that this implies that for fixed $y \ge 2$, the probability $S_2(x,y)/\Psi(x,y)^2$ decays like $1/\Psi(x,y) \asymp (\log x)^{-\pi(y)}$.

  • For $x \ge y \ge 2$ with $y/\log x \to 0$ as $ x \to \infty$, we have $\Psi(x,x,y) = \Psi(x,y)^{1+o(1)}$.

  • For $x \ge y \ge 2$ with $y/\log x \to \infty$ we have $\Psi(x,x,y)=\Psi(x,y)^{2+o(1)}$ as $x \to \infty$.

  • For $x \ge y \ge (\log x)^{2+\varepsilon}$ we have $\Psi(x,x,y) \sim \Psi(x,y)^2/\zeta(2\alpha)$ as $x \to \infty$ where $\alpha$ is the saddle point associated with $x$ and $y$. (I'll include a proof below.)

This leaves out the range $y \asymp \log x$, which is the main focus of Granville's paper. In Theorem 3 he proves an asymptotic formula in this remaining case.


Below I explain how one treats the case where $y$ grows sufficiently fast with $x$ (namely, $y \ge (\log x)^{1+1/(k-1)+\varepsilon}$, but I'll start with a general discussion. 

First of all, in this case it is often useful to introduce a truncation parameter $T>0$ into the above inclusion-exclusion formula, and obtain via the union bound the estimate $$ (\star)\, S_k(x, y) = \sum_{d \text{ is }T\text{-smooth}} \mu(d) \Psi(x/d,y)^k + O\left( \sum_{y\ge p > T} \Psi(x/p,y)^k \right).$$ The ratio $\Psi(x/d,y)/\Psi(x,y)$ (`local density') was studied extensively in the literature, namely in

These papers prove either asymptotic results or bounds on $\Psi(x/d,y)/\Psi(x,y)$ in terms of $d^{-\alpha}$ where $\alpha\in (0,1)$ is a certain 'saddle point' defined in terms of $x$ and $y$. Below is a quick lemma one can prove using the paper of Ivić and Tenenbaum, which is quite powerful when $y$ is not too smallthe strategy hinted by Granville.

Corollary: Fix $k \ge 2$. Suppose $x \ge y$ and that $y$ grows with $x$ faster than any power of $\log x$ (i.e. $\log y /\log \log x \to \infty$). Then $$\frac{S_k(x,y)}{\Psi(x,y)^k} \sim 1/\zeta(k)$$$$\frac{S_k(x,y)}{\Psi(x,y)^k} \sim \zeta(k)^{-1}$$ as $x \to \infty$.

Lemma: Fix $k \ge 2$. Suppose $x \ge y \ge (\log x)^{1 + \frac{1}{k-1}+\varepsilon}$ for some $\varepsilon>0$. Then $$(\star \star)\, \frac{S_k(x,y)}{\Psi(x,y)^k} \sim \prod_{p}\left(1-p^{-k\beta(x,y)}\right)$$$$(\star \star)\, \frac{S_k(x,y)}{\Psi(x,y)^k} \sim \zeta(k\beta(x,y))^{-1}$$ as $x \to \infty$, where $\beta:=1-\frac{\xi(u)}{\log y}$, $u:=\log x / \log y$ and $\xi(u)\sim \log u$ is defined via $e^{\xi(u)}-1=\xi(u)$. In particular, the infinite product in $(\star \star)$ is bounded away from $0$.

Let me formalize the problem and give some results. iv A number $n$ is $y$-smooth (or $y$-friable) if all its prime factors $p$ are less than or equal to $y$. Let us set $$\Psi(x,y) :=\# \{ n \le x: n \text{ is }y\text{-smooth}\},$$ which appeared in Sungjin Kim's comment. One can consider the quantity $$S_k(x,y) := \# \{ n_1,\ldots,n_k \le x: \gcd(n_1,n_2,\ldots,n_k)=1, \, n_i \text{ is }y\text{-smooth}\}.$$ The ratio $S_k(x,y)/\Psi(x,y)^k$ is exactly the probability that $n$ positive integers chosen uniformly at random from the set of $y$-smooth numbers up to $x$ have no non-trivial common factor. Equivalently, it is the probability that a vector of $y$-smooth numbers and $L^1$-norm $\le x$ is visible from the origin.

Below I discuss what happens if $y$ is allowed to grow with $x$. First of all, in this case it is often useful to introduce a truncation parameter $T>0$ into the above inclusion-exclusion formula, and obtain via the union bound the estimate $$ (\star)\, S_k(x, y) = \sum_{d \text{ is }T\text{-smooth}} \mu(d) \Psi(x/d,y)^k + O\left( \sum_{y\ge p > T} \Psi(x/p,y)^k \right).$$ The ratio $\Psi(x/d,y)/\Psi(x,y)$ (`local density') was studied extensively in the literature, namely in

These papers prove either asymptotic results or bounds on $\Psi(x/d,y)/\Psi(x,y)$ in terms of $d^{-\alpha}$ where $\alpha\in (0,1)$ is a certain 'saddle point' defined in terms of $x$ and $y$. Below is a quick lemma one can prove using the paper of Ivić and Tenenbaum, which is quite powerful when $y$ is not too small.

Corollary: Fix $k \ge 2$. Suppose $x \ge y$ and that $y$ grows with $x$ faster than any power of $\log x$ (i.e. $\log y /\log \log x \to \infty$). Then $$\frac{S_k(x,y)}{\Psi(x,y)^k} \sim 1/\zeta(k)$$ as $x \to \infty$.

Lemma: Fix $k \ge 2$. Suppose $x \ge y \ge (\log x)^{1 + \frac{1}{k-1}+\varepsilon}$ for some $\varepsilon>0$. Then $$(\star \star)\, \frac{S_k(x,y)}{\Psi(x,y)^k} \sim \prod_{p}\left(1-p^{-k\beta(x,y)}\right)$$ as $x \to \infty$, where $\beta:=1-\frac{\xi(u)}{\log y}$, $u:=\log x / \log y$ and $\xi(u)\sim \log u$ is defined via $e^{\xi(u)}-1=\xi(u)$. In particular, the infinite product in $(\star \star)$ is bounded away from $0$.

This question, at least for $k=2$, was studied by Gunderson, Coppersmith and Granville. Surprisingly, the motivation has to do with the first case of Fermat's Last Theorem, but I won't elaborate on that. See specifically Granville's paper "On positive integers $\le x$ with prime factors $\le t \log x$" (Number Theory and Applications (ed R.A. Mollin) (Kluwer, NATO ASI, 1989), pages 403-422, PDF link).

Let me formalize the problem and explain some some results.

A number $n$ is $y$-smooth (or $y$-friable) if all its prime factors $p$ are less than or equal to $y$. Let us set $$\Psi(x,y) :=\# \{ n \le x: n \text{ is }y\text{-smooth}\},$$ which appeared in Sungjin Kim's comment. One can consider the quantity $$S_k(x,y) := \# \{ n_1,\ldots,n_k \le x: \gcd(n_1,n_2,\ldots,n_k)=1, \, n_i \text{ is }y\text{-smooth}\}.$$ The ratio $S_k(x,y)/\Psi(x,y)^k$ is exactly the probability that $n$ positive integers chosen uniformly at random from the set of $y$-smooth numbers up to $x$ have no non-trivial common factor. Equivalently, it is the probability that a vector of $y$-smooth numbers and $L^1$-norm $\le x$ is visible from the origin.

In Granville's paper linked above, he studies the quantity $\Psi(x,x',y)$, which counts pairs $(a,b)$ of coprime $y$-smooth integers with $a \le x$ and $b\le x'$. For $x'=x$, $\Psi(x,x,y)$ is precisely $S_2(x,y)$. In pages 8--9 he quickly derives the following results, and the arguments should extend to $S_k(x,y)$:

  • For $2 \le y \le (\log x)^{1/2}$, we have $\Psi(x,x,y) \sim \binom{2\pi(y)}{\pi(y)} \Psi(x,y)$ as $x \to \infty$. Note that this implies that for fixed $y \ge 2$, the probability $S_2(x,y)/\Psi(x,y)^2$ decays like $1/\Psi(x,y) \asymp (\log x)^{-\pi(y)}$.

  • For $x \ge y \ge 2$ with $y/\log x \to 0$ as $ x \to \infty$, we have $\Psi(x,x,y) = \Psi(x,y)^{1+o(1)}$.

  • For $x \ge y \ge 2$ with $y/\log x \to \infty$ we have $\Psi(x,x,y)=\Psi(x,y)^{2+o(1)}$ as $x \to \infty$.

  • For $x \ge y \ge (\log x)^{2+\varepsilon}$ we have $\Psi(x,x,y) \sim \Psi(x,y)^2/\zeta(2\alpha)$ as $x \to \infty$ where $\alpha$ is the saddle point associated with $x$ and $y$. (I'll include a proof below.)

This leaves out the range $y \asymp \log x$, which is the main focus of Granville's paper. In Theorem 3 he proves an asymptotic formula in this remaining case.


Below I explain how one treats the case where $y$ grows sufficiently fast with $x$ (namely, $y \ge (\log x)^{1+1/(k-1)+\varepsilon}$, but I'll start with a general discussion. 

First of all, in this case it is often useful to introduce a truncation parameter $T>0$ into the above inclusion-exclusion formula, and obtain via the union bound the estimate $$ (\star)\, S_k(x, y) = \sum_{d \text{ is }T\text{-smooth}} \mu(d) \Psi(x/d,y)^k + O\left( \sum_{y\ge p > T} \Psi(x/p,y)^k \right).$$ The ratio $\Psi(x/d,y)/\Psi(x,y)$ (`local density') was studied extensively in the literature, namely in

These papers prove either asymptotic results or bounds on $\Psi(x/d,y)/\Psi(x,y)$ in terms of $d^{-\alpha}$ where $\alpha\in (0,1)$ is a certain 'saddle point' defined in terms of $x$ and $y$. Below is a quick lemma one can prove using the paper of Ivić and Tenenbaum, which is the strategy hinted by Granville.

Corollary: Fix $k \ge 2$. Suppose $x \ge y$ and that $y$ grows with $x$ faster than any power of $\log x$ (i.e. $\log y /\log \log x \to \infty$). Then $$\frac{S_k(x,y)}{\Psi(x,y)^k} \sim \zeta(k)^{-1}$$ as $x \to \infty$.

Lemma: Fix $k \ge 2$. Suppose $x \ge y \ge (\log x)^{1 + \frac{1}{k-1}+\varepsilon}$ for some $\varepsilon>0$. Then $$(\star \star)\, \frac{S_k(x,y)}{\Psi(x,y)^k} \sim \zeta(k\beta(x,y))^{-1}$$ as $x \to \infty$, where $\beta:=1-\frac{\xi(u)}{\log y}$, $u:=\log x / \log y$ and $\xi(u)\sim \log u$ is defined via $e^{\xi(u)}-1=\xi(u)$. In particular, the infinite product in $(\star \star)$ is bounded away from $0$.

added 320 characters in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading
added 164 characters in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading
deleted 380 characters in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading
added 290 characters in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading
added 1 character in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading
added 164 characters in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading
added 164 characters in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading
added 487 characters in body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79
Loading