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, ...
- 121
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 ...
- 39
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
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:
$$...
- 435
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. ...
- 47
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
-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 ...
- 47
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 ...
- 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 ...
- 47
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
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$ ...
- 1,776
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, ...
- 654
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$ ...
- 5,470
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 ...
- 47
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
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(\...
- 715
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
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} ...
- 255
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
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
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 ...
- 6,984
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 ...
- 26.9k
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\...
- 1,352
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 ...
- 48.9k
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
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 ...
- 1,101
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
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
11
votes
2
answers
1k
views
Heuristic lower bounds on small sums of roots of unity
Let $f(k,n)$ be the smallest non-zero absolute value of a sum of $k$ complex $n$th roots of unity. Asking for bounds in either direction, Tao suggested that a polynomial lower bound seemed plausible ...
- 4,589
5
votes
2
answers
873
views
Exact formula for partial sums of Liouville function $L(n)$ (OEIS sequence A002819)
I am wondering if it is possible to get a useful exact formula, or at least some useful asymptotics, for the partial sums of the Liouville function (OEIS sequence A002819)
$$L(n)=\sum_{k=1}^n \lambda(...
- 3,098
8
votes
2
answers
387
views
Are we able to estimate the fraction of the domain where $\cos (ax)+2\cos (b x)$ with $\frac ab \notin\mathbb{Q}$ is positive?
We know that the two functions $\{\;\cos (ax),\;2\cos (b x)\;\}$ where $\frac ab \notin \mathbb{Q}$ are independently positive (and negative) over $\frac 12$ of the domain.
Is it possible to estimate ...
user215601
14
votes
1
answer
1k
views
Normal numbers, Liouville function, and the Riemann Hypothesis
This is a question about whether or not some number $\lambda^*$ is normal in base 2. More specifically, I am wondering if $\lambda^*$ is not normal. Proving it is normal would be next to impossible, ...
- 3,098
5
votes
3
answers
601
views
Convergence speed of a random dyadic rational generator
We are given a multiset $M$ of real numbers which initially is equal to $\{0,1\}$. In a sequential fashion, at each round $r\in\mathbb{N}$
two distinct instances $x_r$ and $y_r$ of $M$'s numbers are ...
- 1,677
1
vote
0
answers
193
views
Theoretical invariant distribution of discrete dynamical systems, including the Riemann Zeta map
Update on 3/10/2021: I added Example 5 in the Appendix. This generic example encompasses the Riemann Zeta dynamical system. A simple version of this post, targeted to engineers, machine learning ...
- 3,098
3
votes
1
answer
315
views
Distribution of the first occurrence of a maximum (record) run of zeros in the digits of a normal number (say $\pi$)
If the question was stated to appeal to the general public, it would be something like this. For a number such as $\pi$ or $\sqrt{2}$, the digits in base $b$ appear to be randomly distributed. We are ...
- 3,098
7
votes
1
answer
430
views
What makes Gaussian distributions special? Local field version?
This question is inspired by the recent one about Gaussian measures over the reals:
What makes Gaussian distributions special?
I would be interested in a similar list of characterizations for the ...
