# Questions tagged [probabilistic-number-theory]

The probabilistic-number-theory tag has no usage guidance.

48
questions

**0**

votes

**1**answer

205 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(...

**2**

votes

**0**answers

95 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 ...

**3**

votes

**0**answers

150 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 ...

**0**

votes

**0**answers

147 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 ...

**0**

votes

**2**answers

117 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 ...

**4**

votes

**1**answer

319 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 ...

**4**

votes

**1**answer

174 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 ...

**1**

vote

**1**answer

149 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(...

**2**

votes

**0**answers

141 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 ...

**0**

votes

**1**answer

102 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,...

**6**

votes

**0**answers

163 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 ...

**2**

votes

**1**answer

137 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 ...

**3**

votes

**4**answers

275 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 (...

**0**

votes

**0**answers

82 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(...

**1**

vote

**0**answers

80 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-...

**1**

vote

**0**answers

128 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 ...

**5**

votes

**1**answer

390 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 ...

**1**

vote

**0**answers

44 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(...

**3**

votes

**0**answers

156 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 ...

**-1**

votes

**2**answers

220 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=...

**3**

votes

**0**answers

124 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,...

**1**

vote

**0**answers

127 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$$
...

**1**

vote

**1**answer

206 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 ...

**2**

votes

**2**answers

706 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/...

**9**

votes

**2**answers

195 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. ...

**4**

votes

**0**answers

306 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 ...

**3**

votes

**1**answer

169 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]$ ...

**3**

votes

**0**answers

206 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 ...

**4**

votes

**2**answers

371 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 ...

**-3**

votes

**2**answers

482 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 ...

**3**

votes

**0**answers

212 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 ...

**13**

votes

**2**answers

683 views

### Number of distinct factors

Denote $\omega(m)$ to be number of distinct factors of $m$ as defined in http://mathworld.wolfram.com/DistinctPrimeFactors.html.
At every $c>0$, given $n\in\Bbb N$ define $$S(n,c)=\big\{m\in\Bbb N:...

**5**

votes

**1**answer

444 views

### How many random matrices does it take to generate a matrix algebra?

Let $\mathbb{F}$ be a finite field.
Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra.
Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$
that one needs to take ...

**18**

votes

**1**answer

1k views

### How many integers divide a number that involves just three non-zero digits?

Just to be concrete, consider the digits to be binary. Hasse showed that among all the primes, only a fraction of $17/24 < 1$ divide a number of the form $2^n+1$. As a result, the integers that ...

**9**

votes

**0**answers

344 views

### In which orders can the numbers of prime factors of consecutive integers be?

Let $\omega(m)$ be the number of distinct prime divisors of a positive integer $m>1$. I am interested in the relative orders in which the numbers $\omega(n+1),...,\omega(n+k)$ can occur.
Given a ...

**3**

votes

**1**answer

385 views

### Ratio of consecutive divisors and average

Let $2\leq d_1 < d_2,...,d_l < n$ be all the proper nontrivial divisors of $n$. I like to understand how much these divisors deviates from each other. Here are two questions in this regard:
(1) ...

**4**

votes

**1**answer

549 views

### Distribution function for divisors of an Integer

For a fixed $n$, let $D_n(x) = \{ d|n : d \leq x \}$ . We assume here $p \leq x \leq n/p$,
where $p$ is the smallest prime factor of $n$.
For example if $n = p^i$ for some prime $p$ then $D_n(x) \...

**2**

votes

**1**answer

181 views

### expected number of shared 1s between two binary strings from a given set

Let say, I have two binary strings with length N, chosen from a set where there are $2^N-K,(K \ge 0)$ independent strings. What would be the expected number of Ones at the same index from two randomly ...

**11**

votes

**2**answers

6k views

### Convergence of moments implies convergence to normal distribution

I have a sequence $\{X_n\}$ of random variables supported on the real line, as well as a normally distributed random variable $X$ (whose mean and variance are known but irrelevant). I know that the ...

**1**

vote

**0**answers

134 views

### Relation between the densities of two functions and their additive convolution?

Suppose that for two integral-valued arithmetic functions $f_i$ ($i=1,2$), the following values are known:
$$ \lim_{n\to \infty} \frac{ \{n:f_i(n) \text{ is odd}\}\cap \{0,1,\ldots, n-1\} }{n}.$$
(In ...

**3**

votes

**2**answers

441 views

### using distribution of primes to generate random bits?

In his popular science book The Music of the Primes, Marcus du Sautoy tries to link the truth of the Riemann Hypothesis to the "randomness" of the primes. To do this, he invokes the idea of a "fair ...

**2**

votes

**1**answer

218 views

### Has every divisibility-antichain density zero?

Let $A \subset \mathbb N$ be a antichain with respect to divisibility. Does this imply that the density of $A$ is $0$?

**24**

votes

**2**answers

1k views

### Drawing natural numbers without replacement.

Suppose we start with an initial probability distribution on $\mathbb{N}$ that gives positive probability to each $n$. Let's call this random variable $X_1$ so we have $P(X_1=n)=p_{1,n}>0$ for all $...

**3**

votes

**1**answer

400 views

### Work exploring application of probability to metric number theory problems

I am interested in studying the application of probabilistic tools to study metric number theoretic problems, specifically the Duffin-Schaeffer conjecture (http://www.math.osu.edu/files/duffin-...

**25**

votes

**2**answers

2k views

### Is there any sense in which Dirichlet density is “optimal?”

A philosopher asked me an interesting math question today! We know that there are sets S of integers which don't have a "natural" or "naive" density -- that is, the quantity (1/n)|S intersect [1..n]| ...

**13**

votes

**1**answer

1k views

### Heuristic reason for Polya's conjecture

Let $\lambda(n)$ be Liouville's function, so that for each positive integer $n = p_1^{m_1}\cdots p_r^{m_r}$, we have that $\lambda(n) = (-1)^{\sum^{r}_{k=1}{m_k}}$. In 1919, Polya conjectured that $L(...

**10**

votes

**1**answer

762 views

### U(3) Sato-Tate measure.

An undergraduate is performing some computations, related to a Sato-Tate conjecture of $U(3)$ type (a curve over $Q$, for which the roots of local L-functions look like eigenvalues of a random matrix ...

**16**

votes

**1**answer

657 views

### What's the probability that k + n^2 is squarefree, for fixed k?

While playing around with this question (when is the sum of two squares squarefree?), from some experimental computations (and bolstered by the fact that the density of squarefree positive integers is ...