Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [probabilistic-number-theory]

4
votes
1answer
205 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 ...
0
votes
0answers
74 views

Probabilistic Howgrave-Graham Bounds with Coppersmith Technique?

Howgrave-Graham condition says roots of $$f(x_1,\dots,x_n)\equiv0\bmod R$$ at an $R\in\mathbb N$ are roots of $$f(x_1,\dots,x_n)=0$$ over $\mathbb Z$ if $$\|f(x_1X_1,\dots,x_nX_n)\|<\frac{R}{\sqrt{\...
1
vote
0answers
40 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
0answers
145 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
2answers
204 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
0answers
118 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
0answers
109 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
1answer
181 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
2answers
692 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
2answers
183 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
0answers
264 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 ...
0
votes
0answers
87 views

Probability distribution associated with total divisors of an integer

Is there a generalization to https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem which gives distribution function for $$\omega(n)=\big|\{d\in\mathsf{prime}:d|n\}\big|$$ where $\mathsf{prime}$...
3
votes
1answer
167 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
0answers
193 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
2answers
331 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
2answers
388 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
0answers
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
2answers
628 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:...
2
votes
0answers
265 views

A variant frobenius problem

From Sylvester's theorem we know that using only coins of sizes $a,b$, we can change exactly $\frac{(a-1)(b-1)}2$ different big coins up to $(a-1)(b-1)$. Denote sets $$\mathcal{S_1}=[c_1n,d_1n]\cap\...
5
votes
1answer
411 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 ...
17
votes
1answer
994 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 ...
8
votes
0answers
292 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
1answer
337 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
1answer
478 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
1answer
167 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 ...
8
votes
2answers
4k 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
0answers
133 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
2answers
437 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
1answer
217 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$?
22
votes
2answers
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
1answer
382 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
2answers
1k 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]| ...
12
votes
1answer
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
1answer
725 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
1answer
633 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 ...