Skip to main content

Questions tagged [probabilistic-number-theory]

Filter by
Sorted by
Tagged with
1 vote
0 answers
76 views

In the modular exponentiation, as used with the adaptive root problem, how to chose the best base that will yield as few results as possible?

Let $n,m,w\in\Bbb N$ and $\lambda\in\Bbb P$ such that $w^\lambda \mod m = n$, with the requirements: $\lambda$ being a random large prime such as $w^\lambda > 2\times m$ $1 < n < m−1$. m is ...
user2284570's user avatar
1 vote
0 answers
166 views

Integers with $k$ prime factors, in terms of the Möbius function

A $k$-free integer is an integer $n$ such that there is no $k$th power dividing $n$. It is well known (see Murty's Problems in Analytic Number Theory q1.18 for instance) that \begin{equation}\sum_{d^k|...
alidixon222's user avatar
2 votes
1 answer
75 views

Existence of an $\alpha$-regular measure with positive measure on a binary digits do not have a limiting frequency

let $$X=\left\{ \sum_{n=1}^{\infty}a_{n}2^{-n}:a_{n}\in\left\{ 0,1\right\} ,\liminf\frac{1}{n}\sum_{i=1}^{n}a_{i}<\limsup\frac{1}{n}\sum_{i=1}^{n}a_{i}\right\} $$ I'm studying fractal geometry and ...
Simple Conjugate's user avatar
4 votes
1 answer
229 views

Asymptotic density of an infinite union of subgroups

Let $1 < a_1 < a_2 < a_3 <{} ...$ be a sequence of integers. For a subset $A \subset \Bbb Z$, denote by $d(A)$ its natural density (if it exists). Is it true that $$ \lim_{N \to +\infty} ...
Alphonse's user avatar
  • 255
2 votes
0 answers
67 views

Twin prime distribution centering twice a semiprime

What is the conjectured distributional behavior of semiprimes $pq$ ($p$ and $q$ are primes) having the property $2pq+1$ and $2pq-1$ are primes?
Turbo's user avatar
  • 13.8k
1 vote
0 answers
63 views

Distribution of number of prime factors of $p^k\pm1$

What is the behavior of number of prime factors of integers of form $p^k\pm1$ where $p$ is a fixed odd prime or $2$ and $k$ varies over positive integers?
Turbo's user avatar
  • 13.8k
1 vote
1 answer
105 views

Why is $\sum_{m=1}^{n}\frac{(\nu(m)-\log\log n)^2}{n\log\log n}=\int_{-\infty}^{\infty}\omega^2\, \mathrm{d}\sigma_n(\omega)$?

I was reading an article on Probabilistic Number Theory by M.Kac where I am not able to understand why a particular equation mentioned here in page $657$ equation $(7.7)$ is true? I do understand that ...
Anish Ray's user avatar
  • 311
3 votes
0 answers
114 views

Choose a sub series of a random series, such that its expectation can be a given real number

Suppose $a>0$, and we have an infinite series of Bernoulli random variables $B_k$ with $$\mathbb{Pr}{\large[}B_k=1{\large]} = \frac{1}{1+e^{a\cdot 2^k}}$$ Then $$\text{E}\left[\sum_{k=-\infty}^{\...
Jone Sweden's user avatar
2 votes
1 answer
529 views

Is there a Cramer's conjecture for Sophie Germain primes?

A prime $q$ such that $2q+1$ is also a prime is a Sophie Germain prime. Cramer's conjecture tells gap between consecutive primes is bound by $O(\log^2p)$. Is there a similar conjecture for Sophie ...
Turbo's user avatar
  • 13.8k
1 vote
0 answers
120 views

On probability of coprimality of a list of numbers

We know $r$ randomly chosen integers are coprime with probability $\frac1{\zeta(r)}$. Pick a bound $N$ and pick $k\lceil N^{\alpha}\rceil$ uniformly random integers in $[0,N^{\alpha+\beta}]$ where $\...
Turbo's user avatar
  • 13.8k
4 votes
1 answer
326 views

Is there an Erdős–Kac theorem for number of divisors?

Erdős–Kac theorem gives average number of prime factors of an integer. Is there a theorem which concerns average number of divisors of an integer?
Turbo's user avatar
  • 13.8k
6 votes
2 answers
2k views

Freeman Dyson's approach to string theory [closed]

Context: In celebrating the centenary of Ramanujan's birth, Freeman Dyson presented the following career advice for talented young physicists [1]: My dream is that I will live to see the day when our ...
Aidan Rocke's user avatar
  • 3,823
2 votes
1 answer
131 views

Is $\lim_{s \rightarrow 1} E(f(X_s)) = \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{k=1}^N f(k)$?

Let $s>1$ be a real number. We look at the zeta probability function / Zipf probability function defined as: $$P(X = n) = \frac{1}{n^s \zeta(s)}$$ Suppose $f: \mathbb{N} \rightarrow \mathbb{R}$ is ...
mathoverflowUser's user avatar
2 votes
0 answers
95 views

Primes as expected values?

This is a follow-up question, which is related to the answer of this quesiton: Is there a connection of prime numbers and extreme value theory? I will duplicate the answer here, so this question is ...
mathoverflowUser's user avatar
8 votes
2 answers
637 views

Ways of proving normal distribution (with a view towards Selberg's central limit theorem)

Given an random variable $Y:\Omega \to \mathbb{R}$ with finite mean $\mu$ and finite, positive variance $\sigma^2$, let $X = \frac{Y-\mu}{\sigma}$ be the renormalization with mean $0$ and variance $1$....
Anurag Sahay's user avatar
  • 1,282
4 votes
0 answers
198 views

Maximum entropy methods for probabilistic number theory

Might there be a good survey paper on the application of maximum entropy inference for non-trivial problems in probabilistic number theory? So far I am aware of the work of Ioannis Kontoyiannis, an ...
Aidan Rocke's user avatar
  • 3,823
2 votes
0 answers
108 views

Erdős–Kac and Poisson

This Wikipedia article tells us that the Erdős–Kac theorem says that if $\omega$ is the number of distinct prime factors of $n$ then: loosely speaking, the probability distribution of $$ \frac{\omega(...
Michael Hardy's user avatar
6 votes
1 answer
370 views

Almost evenly distributed spherical random vectors

Consider $n$ i.i.d spherically distributed random vectors $z_1 ,\cdots , z_n \sim \text{Unif}(\mathbb{S}^{d-1})$. What is the best lower bound on $n$ for which whp there exists a constant $c>0$ ...
Sina Baghal's user avatar
0 votes
1 answer
168 views

Upper bound for an infinite series of Pochhammer Symbol

Let $a_n = \frac{1}{n!}\prod_{i=0}^{n-1} (r+\alpha i)$, for constants $0<r, \alpha<1$. The series is convergent by the ratio test. I want to find the exact value or maybe an upper bound for the ...
moonlight's user avatar
0 votes
1 answer
247 views

How differently would we model the distribution of primes if prime gap is larger?

Cramer's conjecture based on his random model provides prime gaps are bound by $O(\log^2p_n)$ where the gap is between $(n+1)$th and $n$th prime. How differently would primes be modeled if gaps of $O(...
Turbo's user avatar
  • 13.8k
2 votes
0 answers
157 views

The uniform “probability” on $\mathbf{N}$: What occurs beyond logarithmic density?

This is a follow-up to Question #47134. There is obviously no uniform probability distribution on $\mathbf{N}$ (or $\mathbf{Z}$); however, using the notion of amenability, you can show that any ...
Rémi Peyre's user avatar
3 votes
0 answers
168 views

Kubilius model in higher sieve dimension?

The Kubilius model, based on the fundamental lemma of sieve theory, let us approximate the probability of events depending on the variables $X_p$, $p\leq y$, where $X_p=1$ if $p|n$ ($n$ a random ...
H A Helfgott's user avatar
  • 19.3k
0 votes
0 answers
152 views

On the $\mathsf{LCM}$ of a set of integers defined by moduli of powers

For integers $a,b,t$ define $$\mathcal R_t(a,b)=\{q\in\mathbb Z\cap[1,\min(a^t,b^t)]: a^t\equiv b^t\bmod q\}$$ and $\mathsf{LCM}(\mathcal R_t(a,b))$ to be $\mathsf{LCM}$ of all entries in $\mathcal ...
VS.'s user avatar
  • 1,826
0 votes
2 answers
181 views

A variant of Turán–Kubilius inequality

Let $\omega(n)$ the number of distinct prime factors of $n$ (counted without multiplicity). A famous consequence of Turán–Kubilius inequality is $$ \sum_{n\leq x}(\omega(n)-\log\log x)^2=O(x\log \log ...
Jean's user avatar
  • 515
9 votes
2 answers
685 views

Is there a connection of prime numbers and extreme value theory?

As most others are, so am I fascinated by primes. By the theorem of Euclid and the sieve of Eratosthenes the $ k \ge 2$ - th prime is given by: $$ p_k = \min_{x>1,\gcd(x,p_1 \cdots p_{k-1})=1} x ...
user avatar
4 votes
1 answer
188 views

Small linear relations between primitive Pythagorean triples $\mathsf{II}$

WillJagy answered a linear relation question on Pythagorean Triples in Small linear relations between primitive Pythagorean triples $\mathsf I$. Now let $a^2+b^2=c^2$ be a primitive Pythagorean ...
VS.'s user avatar
  • 1,826
1 vote
1 answer
170 views

Small linear relations between primitive Pythagorean triples $\mathsf I$

Say $a^2+b^2=c^2$ is a primitive Pythagorean triple. Then consider the Linear Diophantine Equation $$ua^2+vb^2+xab+ybc+zca=0$$ where $(u,v,x, y, z)\in\mathbb Z^4$ are variables. If $(u,v,x, y, z)\neq(...
VS.'s user avatar
  • 1,826
2 votes
0 answers
170 views

Funny questions about Moebius Function

I need to firstly claim that my research is not about number theory, however, I am pretty interested in it, especially funny questions in number theory, e.g. Kollatz Conjecture. Three years ago, I ...
cheng's user avatar
  • 41
0 votes
1 answer
128 views

Probabilistic interpretation of square free numbers and other properties

We can use the Lindberg condition to show the distribution of number of prime divisors of an integer approaches Gaussian. Is there a similar probabilistic formulation for square free numbers? That is,...
VS.'s user avatar
  • 1,826
6 votes
0 answers
198 views

Smooth integers with lower bound on $\omega(n)$

Define $(b,c)$-smooth integers to be integers having all prime factors bigger than $c$ and smaller than $b$. Probability a number is $(b,1)$-smooth is governed by the Dickman function while ...
VS.'s user avatar
  • 1,826
2 votes
1 answer
150 views

Non-asymptotic results in probabilistic number theory

I'm a beginner. When I searched for results in probabilistic number theory most of the results were asymptotic in nature. Are there any results like with probability 1-$\epsilon$ (w.h.p) some property ...
user221985's user avatar
3 votes
4 answers
280 views

Approximately satisfying simultaneous vector linear diophantine equations?

Pick three $a,b,c$ vectors in $\mathbb Z^n$ uniformly with $\max(\|a\|_\infty,\|b\|_\infty)<T$ and $\|c\|_\infty<T^2$ and an $\epsilon>0$. Assume $a$ and $b$ are coordinatewise coprime (...
Turbo's user avatar
  • 13.8k
0 votes
0 answers
84 views

Deterministically finding a subsequence of integers matching modular roots?

Take two integers $n$ and $m$ with $0<\log_2m<n<m$ and let $r_1=f_1(n)\bmod m$ and $r_2=f_2(n)\bmod m$ for functions $f_1,f_2:\mathbb Z\rightarrow\mathbb Z$. Denote the $\ell$ roots of $(f_i(...
Turbo's user avatar
  • 13.8k
1 vote
0 answers
88 views

What is the probability of 'yes' to this likely $coNP$ problem?

Pick a set of primitive (gcd of coordinates is $1$) integer points $\mathcal T$ in $\mathbb Z^n$. Denote the set of $n$ many algebraically independent homogeneous system of polynomials (thus zero-...
VS.'s user avatar
  • 1,826
1 vote
0 answers
132 views

Probability of small solutions to an uniform random linear diophantine equation?

Take the set $$T(c_1,\dots,c_t)=\{(x_1,\dots,x_t)\in\mathbb Z^t\backslash\{(0,\dots,0)\}:\sum_{i=1}^tc_ix_i\equiv0\bmod q\}$$ where $c_1,\dots,c_t\in(-q/2,q/2)\cap\mathbb Z$. What is probability ...
Turbo's user avatar
  • 13.8k
5 votes
1 answer
419 views

How many roots of polynomial in $\mathbb Z[x]$ and $\mathbb Q[x]$ are integers on average?

Given $d,B>0$ the number of polynomials in $\mathbb Z[x]$ of degree $d$ and coefficient size at most $B$ have at least one integer roots should be $B^{O(d)}f(d)$ at some function $f$ (from Random ...
Turbo's user avatar
  • 13.8k
1 vote
0 answers
47 views

Does a weighted sequence derived from a sequence matching the Siegel lemma BV bound behave as an uniformly random sequence?

Pick integers $r_1',\dots,r_t'$ that achieve the Bombieri Vaaler bound for the Siegel lemma and find an $m$ (it exists by Dirichlet Pigeonhole) such that given prime $T$ gets $m(r_1',\dots,r_t')\equiv(...
Turbo's user avatar
  • 13.8k
3 votes
0 answers
160 views

Modular root of $-1$

Take two distinct coprime integers $a,b$ and take $q=a^2+b^2$. Consider the equation $(xy^{-1})^2\equiv-1\bmod q$. The solutions are two roots which correspond to $(x,y)=(a,b)$ and $(x,y)=(b,a)$. Look ...
Turbo's user avatar
  • 13.8k
-1 votes
2 answers
231 views

On distribution of size of integer points in a subspace associated to a linear diophantine equation

Take $A,B,C,D$ pairwise coprime with $$n<A,B,C,D<2n$$ $$ n/4<|A−B|,|C−D|,|A−C|,|A−D|,|B−C|,|B−D|$$ and consider the space of solutions to $ACa+ADb+BCc+BDd=0$ spanned by $3\times 4$ matrix $$N=...
Turbo's user avatar
  • 13.8k
3 votes
0 answers
129 views

Improving prime number generation probability?

Deterministic generation of primes in polynomial time is unknown. Is there a way to probablistically in $O(n^c)$ time bound for some $c>0$ generate polynomially $\Omega(n^c)$ many integers in $[0,...
Turbo's user avatar
  • 13.8k
1 vote
0 answers
130 views

$L^\infty$ norm lower bound for Integer points in null spaces of recursively defined integer vectors?

Letting $\otimes$ be matrix kronecker/tensor product with $n\in\Bbb N$ as a parameter define non-negative integer vectors recursively $$v_1=\begin{bmatrix}a_1&b_1\end{bmatrix}\in\Bbb Z_{>0}^2$$ ...
Turbo's user avatar
  • 13.8k
1 vote
1 answer
231 views

Generalized notion of divisor function?

Divisor function $d(n,m)$ counts the number of $q\in\Bbb N$ with $b<q<m$ such that $n\bmod q\equiv0$. Given $b>0$ what is the correct asymptotic, probabilistic and average case behavior of ...
Turbo's user avatar
  • 13.8k
2 votes
2 answers
725 views

Occurrence of simultaneous small remainders?

Fix $(a,b)=1$, $a<b<2a$ and $a,b>n^{1/(2t)}$ and fix a prime $T\approx n^{\tau+\frac1k}$ where $\tau\geq1$ and $k=2(t-1)$. We can show using exponential sums there is an $m_{_T}$ such that $T/...
user avatar
9 votes
2 answers
236 views

If normal with respect to prime base then normal for all bases

I tried to find it on internet but couldn't so m asking this here. I want to ask if a number is normal with respect to all prime number base then do we know that it is normal with respect to any base. ...
Himanshu Shukla's user avatar
4 votes
0 answers
323 views

Asymptotic estimate for a random model of primes

Question Let $$ \pi_{rm_c}(x) = \sum_{ \substack{ {n\leq x}\\{(n+a,P(\sqrt{n}))=1}}} 1-1, $$ where $P(x)$ is the product of all primes less or equal to $x$ and $a$ is a random integer constrained to ...
user45947's user avatar
  • 955
3 votes
1 answer
187 views

Exact statistics in the Frobenius coin problem

The Frobenius coin problem guarantees that if $(a,b)=1$, then $$ax+by$$ does not represent exactly $\frac{(a-1)(b-1)}2$ numbers all below $g(a,b)=ab-a-b$ if $x,y\geq0$ holds. Assume $m\in[0,ab-a-b]$ ...
Turbo's user avatar
  • 13.8k
3 votes
0 answers
234 views

Reference request: Darboux properties of real-valued set functions (measures, densities, etc.)

Fix a set $S$ and let $f: \mathcal P(S) \rightharpoonup \mathbf R$ be a real-valued partial function on the power set of $S$; denote by $\mathcal D$ the domain of $f$. We say that $f$ has: (i) the ...
Salvo Tringali's user avatar
4 votes
2 answers
432 views

Relative-totient function (2nd attempt)

Let $\Lambda(x,y)$ be the count of totatives of $x$ that are less than or equal to $y$. I am asking for the following result to be verified, (particularly the final proposal), I have found no ...
Brad Graham's user avatar
-3 votes
2 answers
600 views

The number of totatives to the nth primorial, in an interval shorter than the nth primorial

(The notation of this question will be improved over the next few days, sorry for the lack of clarity at the moment.) Can, and if so when can, we determine the amount of natural numbers which are ...
Brad Graham's user avatar
3 votes
0 answers
227 views

Probability that an integer contains no $1\bmod 4$ prime factor

$n$ represents integer variable. What is the probability that and integer contains at most $r(n)$ prime factors of form $1\bmod 4$ where $r(n)$ is a function of $\omega(n)$ (number of distinct prime ...
user avatar