All Questions
Tagged with pr.probability nt.number-theory
181 questions
1
vote
1
answer
150
views
Resource request (probability theory, computability theory, algebra)
I'm a first year graduate student trying to explore specific topics I might be interested in researching. Currently, I enjoy algebra, probability theory, and the computability theory side of logic, ...
- 236k
1
vote
0
answers
150
views
What are alternative mathematical definitions of observers beyond Bennett and Hoffman's framework?
Motivation:
This question is inspired by a talk from Avi Wigderson given on Randomness, where the idea that the randomness is in the eye of the observer is suggested.
In the study of information ...
- 3,064
2
votes
0
answers
114
views
Echoes of the chord
Just a fun problem I thought of.
A man is playing a magical pipe organ - every chord is an integer number of decibals (dB) loud. The softest chord is $0$ dB. Every chord of $N > 0$ dB creates a ...
- 6,215
3
votes
1
answer
435
views
What is the connection between these three methods of generating this sequence?
I was recently looking at this problem: “There are a number of balls in a jar, some of them red, some of them white. The odds of picking two at random and both balls being red is 1/2. How many of the ...
- 128k
0
votes
0
answers
102
views
Formalizing the "pseudorandomness" of primes
Many conjectures about primes seem to revolve around the idea of "primes are random". So I thought about how this "randomness" may be formally defined, and came up with the ...
- 1
26
votes
5
answers
10k
views
Is there a simple way to compute the number of ways to write a positive integer as the sum of three squares?
It's a standard theorem that the number of ways to write a positive integer N as the sum of two squares is given by four times the difference between its number of divisors which are congruent to 1 ...
- 121
1
vote
0
answers
87
views
Equidistribution of Frobenius Classes
Let $G$ be a reductive group over $\mathbb{Q}$. Let $K$ be a maximal compact subgroup of $G(\mathbb{C})$. Let $S$ be a finite set of primes. For each prime $p$ not in $S$, let $Frob_p$ be a conjugacy ...
- 11
1
vote
0
answers
143
views
Integer points inside the high-dimensional ball (asymptotics)
Let $N(\alpha, n)$ denote the number of integer points inside the origin-centered ball of radius $\alpha \sqrt n$ in $n$ dimensions, where $\alpha \in (0,\infty)$ is some fixed constant. Precisely:
$$...
- 12.9k
0
votes
0
answers
63
views
Arrangements of fixed $k$-polyplets in a $n\times n$ matrix
Recently, I asked a question about the number of arrangements of $k$ elements inside a $n\times n$ matrix with certain restrictions. The one I´m actually interested in for this question is in its 2. ...
- 12.9k
1
vote
0
answers
134
views
Number of ways to place 4 kings on nxn chessboard
I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:
In the case where the $4$...
- 47
2
votes
1
answer
199
views
Average cluster size of a n-size vector
Given a vector of $n$ cells and $k$ elements in it, we can define a cluster of elements as a contiguous sequence of elements inside the vector.
My goal is to calculate the average cluster size for all ...
- 800
-3
votes
1
answer
144
views
Count arrangements with pairs of attacking kings [closed]
I have a $1\times n$ chessboard and $2$ pairs of kings in it. Both components of each pair of kings must be adjacent in the chessboard, that is, they must be attacking.
Now, I want to calculate the ...
- 13.4k
1
vote
1
answer
170
views
Mean of probability distribution
I have a probability distribution defined by the following density function:
$f(k,j,n,m)=\frac{(m n)! \mathcal{S}_k^{(j)}}{(m n)^k (m n-j)!}$ (With $\mathcal{S}_k^{(j)}$ being the Stirling number of ...
- 188k
0
votes
0
answers
55
views
Counting matrix paths for (n,m>2) matrices
Given a $n\times m$ matrix with $k$ elements inside it, I need to calculate the number of arrangements of those $k$ elements that form at least 1 path from the top to bottom matrix row composed of the ...
- 47
7
votes
0
answers
134
views
Why does this oddly nice lognormal shape come out of tree?
I was reading this paper and came across the Euclid tree. For a simple version of this tree, consider an infinite binary tree rooted with the triple $(1,2,3)$. Then for each vertex $(x,y,z)$, its left ...
- 71
2
votes
0
answers
118
views
the projection distribution induced by integral points on the sphere
Let $A=\{\mathbf{v} \in \mathbb{Z}^{n}: \|\mathbf{v}\|^2= m \}$ and a fixed $\mathbf{y}\in \mathbb{R}^n$, the norm here refers to the Euclidean norm.
Suppose $\mathbf{x}$ is a uniform distribution on ...
- 253
13
votes
1
answer
761
views
If $(a,b,c)$ are the sides of a triangle, then the probability $P(ax + by \ge c) = \frac{4}{\pi^2}\chi_2(x) + \frac{4}{\pi^2}\chi_2(y)$
Posting this question in MO since it is unanswered in MSE
Let $(a,b,c)$ be the side of a triangle. In its most general linear form, the triangle inequality can be expressed as: Does $ax + by \ge c$ ...
- 105k
3
votes
1
answer
401
views
Probability of finding a prime number between $x-\ln(x)$ and $x+\ln(x)$
Using my computer, I found that in the interval $[1, N]$ the probability of finding a prime number between $x-\ln(x)$ and $x+\ln(x)$ is greater than constant $c$ where $N=10^2, 10^3,...,10^{9}$, $x$ ...
- 105k
9
votes
1
answer
497
views
Quantum probabilistic method?
The probabilistic method uses arguments from probability to prove deterministic statements. This has been applied to diverse fields such as combinatorics, topology and number theory. In this method, ...
- 188k
4
votes
2
answers
227
views
Given an automatic set $S$ coming from a DFA $M$ when read little-endian, is $\overline{d}(S)$ at most the Büchi acceptance probability of $M$?
Note: I've entirely rewritten this question! Originally it was just the third formulation, take note of that when reading answers.
Let's say $S$ is a $b$-automatic set, and let's say $M$ is a DFA ...
- 2,585
1
vote
0
answers
84
views
Percolative process distribution not equivalent to coupon collector problem distribution
I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...
- 63.9k
6
votes
1
answer
809
views
Probability that a positive integer is in the range of the Euler phi function
Define $f(n) = |\{m : m\le n, \exists k \text{ s.t. }\phi(k) = m\}|$.
Clearly, $f(n)\le \left\lfloor \frac{n}{2}\right\rfloor + 1$ since $\phi(n)$ is even for all $n > 2$.
Is $\limsup_{n\...
- 105k
1
vote
0
answers
78
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 ...
- 87
4
votes
2
answers
307
views
Lower bounding a partition-related sum
We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...
- 43.7k
11
votes
2
answers
758
views
Notions of "independent" and "uncorrelated" for subsets of the natural numbers
In probability/statistics, there is a notion of two things being "independent", which would basically mean that any information we can get about one thing has no effect on our (probabilistic)...
- 14k
4
votes
0
answers
536
views
Is the integer factorization into prime numbers normally distributed?
Edit:
Sorry, for the inconvenience: I have edited the question, since there was a misconception in my thinking.
Let $P_1(n) := 1$ if $n=1$ and $\max_{q\mid n, \text{ } q\text{ prime}} q$ otherwise, ...
- 3,064
3
votes
0
answers
177
views
What is the expected size of the complement of the union of random cosets of the prime ideals of $\mathbb{Z}$?
For each rational prime $p$ let $\mathbf{X}_p$ denote the random variable uniformly distributed in $\{0, 1, ..., p-1\}$, with all the $\mathbf{X}_p$ independent of each other. Define the coset $\...
- 2,858
7
votes
0
answers
222
views
Projected polar chessboard measure convergence in total variation?
$\newcommand\R{\mathbb R}\newcommand\C{\mathbb C}\newcommand\ga{\gamma}$For natural $n$, let $E_n$ be the set of all points in $\R^2$ with "polar coordinates" $(r,t)$ in the set
$$F_n:=\...
- 128k
18
votes
1
answer
872
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 ...
- 23.8k
2
votes
3
answers
1k
views
The probability that a random number N has at least M factors
That is, how to calculate it given the size of N(that is, logN) and assuming that logN is much greater than M. Its an approximation. There is no exact formula.
I do know that according to the prime ...
- 2,821
4
votes
1
answer
239
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} ...
- 1,355
4
votes
0
answers
414
views
Explicit formula for tournament sequence
I am looking for an explicit formula for a sequence. The sequence is generated as follows:
There is a tournament with $10$ teams. In the beginning, all teams have a 0-0 win-loss record. The teams are ...
- 41
30
votes
1
answer
2k
views
Have any numbers been proven to be normal that weren't constructed to be?
It's easy to construct an example of a number that's normal in a given base, but for most given numbers it's notoriously hard to prove that they're normal.
Has any number ever been proven to be normal ...
- 1,311
15
votes
2
answers
5k
views
What areas of algebra could be interesting to probability theorists?
I would like to find some topic of algebra (beyond linear algebra; algebraic number theory is fine) that would be interesting both to a student that wants to specialize in probability theory and to me ...
CommunityBot
- 1
6
votes
4
answers
2k
views
Probability that randomly chosen integers from a restricted set of natural numbers are coprime
We know that the probability $P(k)$ of $k$ randomly chosen integers $(k \ge 2)$ from the set of natural number are coprime is
$$
P(k) = \frac{1}{\zeta(k)}.
$$
I am looking at a special case of ...
2
votes
0
answers
215
views
An approach to the prime number theorem with Rademacher variables and a recursive formula for the prime pi function?
Consider the bipartite graphs defined here:
Why is this bipartite graph a partial cube, if it is?
We do random walks on them with equal propability and since the graphs are finite and connected the ...
- 3,064
17
votes
13
answers
6k
views
Probability in number theory
I am hearing that there are some great applications of probability theory (or more general measure theory) to number theory. Could anyone recommend some good book(s) on that (or other types of ...
- 12.9k
1
vote
0
answers
169
views
Normal numbers and law of the iterated logarithm
If I remember correctly, for the binary digits of a real number in $[0,1]$, I was told that satisfying the law of the iterated logarithm (LIL) is stronger than being normal. That is, supposedly, some ...
- 3,098
2
votes
1
answer
159
views
Is the density of integers $n$ such that the finite sequence $(\omega(n-r)\omega(n+r))_{0\leq r\leq n-1}$ is surjective positive?
Let $\omega(m)$ be the number of prime factors of $m$ regardless of multiplicity. I'm interested in the behavior of the finite sequence $(\omega(n-r)\omega(n+r))_{0\leq r\leq n-1}$ for a given integer ...
- 28.2k
1
vote
0
answers
123
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 $\...
- 13.9k
1
vote
1
answer
183
views
Expectation of edge weights on the complete graph
Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random ...
- 37.7k
2
votes
0
answers
98
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 ...
- 3,064
2
votes
1
answer
197
views
When does a random trigonometric sum approximate $1$?
I am looking for an upper bound $R=R_{n,\varepsilon}$ such that for given $\varepsilon>0$ and real numbers $\alpha_1, \dotsc, \alpha_n$ in, say, $[1,2]$, there is $x\in [1,R]$ such that
$$
\frac 1n\...
- 128k
8
votes
2
answers
671
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$....
- 1,354
15
votes
3
answers
1k
views
Is $\prod_{i=1}^\infty (1-\frac{1}{2^{(2^i)}})$ transcendental?
Motivation. In a coin game, a player flips all their coins every turn, starting with just one coin. If the coins all land heads then the game stops; otherwise, the number of coins is doubled for the ...
- 188k
2
votes
0
answers
87
views
The covariance of certain random variable
We define two random variables $X_n,Y_n $ on the sample space $\{1,2,3,\cdots,n\}$ with counting measure. We denote by $C_n$ the covariance of theses two random variables: $C_n=Cov(X_n,Y_n)$.
...
- 356
0
votes
0
answers
257
views
Unexpected autocorrelations in sequence of primes modulo 4
It is well known that there is a little bias in the distribution of prime residues modulo 4. But the bias eventually vanishes. I looked at the first million primes, and the counts are as follows:
...
- 3,098
1
vote
0
answers
641
views
Some stuff related to the twin prime conjecture
I am making three statements here, and my question is about statement 2, asking if someone can prove or disprove it. A (possibly weaker) version of statement 2 was proved as an answer to a former ...
- 3,098
5
votes
2
answers
707
views
Distribution of some sums modulo p
Fix a finite set of integers $S$ and a prime number $p$. Let $(a_1, a_2, \dotsc, a_n)$, $(b_1, b_2, b_3, \dotsc, b_n)$ be two sequences of integers where the numbers $a_i$ and $b_i$ are chosen ...
- 114k
8
votes
1
answer
380
views
Question about estimating random symmetric sums modulo p
Let $n > 0$ be a positive integer (large) and $p > 2$ a fixed prime number. What is the probability that $$\sum_{ 1 \leq i < j \leq n} a_ia_j = 0 \mod p$$ where $a_1, a_2, \dots a_n$ are ...
- 1,101