All Questions
Tagged with pr.probability nt.number-theory
181 questions
106
votes
5
answers
10k
views
integral of a "sin-omial" coefficients=binomial
I find the following averaged-integral amusing and intriguing, to say the least. Is there any proof?
For any pair of integers $n\geq k\geq0$, we have
$$\frac1{\pi}\int_0^{\pi}\frac{\sin^n(x)}{\...
- 43.2k
66
votes
4
answers
4k
views
Perron number distribution
A Perron number is a real algebraic integer $\lambda$ that is larger than the absolute value of any of its Galois conjugates. The Perron-Frobenius theorem says that any
non-negative integer matrix $M$ ...
- 25.1k
54
votes
4
answers
3k
views
When has the Borel-Cantelli heuristic been wrong?
The Borel-Cantelli lemma is very frequently used to give a heuristic for whether or not certain statements in number theory are true.
For example, it gives some evidence that there are finitely many ...
- 11.4k
44
votes
5
answers
7k
views
Heuristically false conjectures
I was very surprised when I first encountered the Mertens conjecture. Define
$$ M(n) = \sum_{k=1}^n \mu(k) $$
The Mertens conjecture was that $|M(n)| < \sqrt{n}$ for $n>1$, in contrast to the ...
32
votes
3
answers
12k
views
What is the Katz-Sarnak philosophy?
It has been recently mentioned by a speaker (his talk is completely not relevant to random matrix theory/RMT though) that modern statistics, especially random matrices theory, will help solving some ...
- 8,071
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
29
votes
3
answers
3k
views
Perron-Frobenius "inverse eigenvalue problem"
The Perron-Frobenius theorem says that the largest eigenvalue of a positive real matrix (all entries positive) is real. Moreover, that eigenvalue has a positive eigenvector, and it is the only ...
- 2,210
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 ...
- 14k
26
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]| ...
- 19.2k
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 $...
- 551
23
votes
2
answers
2k
views
Parity of $\lfloor 1/(x y) \rfloor$ not equally distributed
A curious puzzle for which I would appreciate an explanation.
For $x$ and $y$ both uniformly and independently distributed in $[0,1]$,
the value of $\lfloor 1/(x y) \rfloor$ has a bias toward odd ...
- 151k
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 ...
- 14k
18
votes
3
answers
1k
views
Not-lonely runners
The lonely runner conjecture
has several formulations.
They all involve a number $n$ runners running on a circular track,
each with a different speeds, and the conjecture is that each runner is ...
- 151k
18
votes
3
answers
918
views
Can Gauss sums derandomize any heuristic arguments?
I've always been fascinated by the fact that the classical Gauss sum has absolute value $\sqrt p$, which is exactly what we would expect if we were to interpret the Gauss sum as a random walk. In ...
- 82.7k
18
votes
0
answers
667
views
The lonely molecule
Suppose $n$ air molecules (infinitesimal points) are bouncing around in
a unit $d$-dimensional cube, with perfectly elastic wall collisions.
Let $k=n^{\frac{1}{d}}$.
For example, in 3D, $d=3$, with $n=...
- 151k
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 ...
16
votes
4
answers
1k
views
Random Diophantine polynomials: Percent solvable?
Suppose one generates a random polynomial
of degree $d$ with integer coefficients
uniformly distributed within $[-c_\max,c_\max]$.
For example, for
$d=8$, $|c_\max|=100$, here is one random polynomial:...
- 151k
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
15
votes
3
answers
2k
views
Probability that product is a perfect square
The probability a given integer in $[0,n]$ is a square is $\frac1{\sqrt n}$. What is the probability that if you take two integers uniformly then their product is square?
I know the main term is $\...
- 13.9k
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 ...
- 16.9k
14
votes
6
answers
2k
views
Density of numbers having large prime divisors (formalizing heuristic probability argument)
I want to prove that the set of natural numbers n having a prime divisor greater than $\sqrt{n}$ is positive.
I have a heuristic argument that this density should be $\log 2$, which is approximately ...
- 7,320
14
votes
3
answers
1k
views
On the number of consecutive divisors of an integer
Define for $n \in \mathbb{N}$ the function $$\tau_1(n):=\sum_{\substack{d|n, \\ d+1|n}}1,$$ i.e. the number of consecutive divisors of an integer. The average of $\tau_1(n)$ is $1$ since $$\sum_{n\leq ...
- 3,062
14
votes
3
answers
1k
views
Probability of coprime polynomials
Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let
$f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ ...
- 54.2k
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
14
votes
1
answer
1k
views
Natural probability on integers
This is a follow-up to this classical question asked recently here: we know (e.g. using the second Borel-Cantelli Lemma) that no probability measure on $\mathbb{Z}$ has the property that $n\mathbb{Z}$ ...
- 14.4k
13
votes
4
answers
1k
views
What results would follow from or imply "randomness" of the primes?
This question on random versions of deterministic problems reminded me that many conditional results in number theory hold if the primes are in some sense random, and it is common knowledge that the ...
13
votes
1
answer
762
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
12
votes
2
answers
820
views
Size of largest square divisor of a random integer
Let $x$ be an integer picked uniformly at random from $1 \ldots N$. Write $x = r^2 t$ where $t$ is square-free. How does the expected value of $r$ scale with $N$? Is anything known about the variance ...
- 1,703
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
11
votes
4
answers
3k
views
If the sum of two independent random variables is discrete uniform on $\{a, \dots,a + n\}$, what do we know about $X$ and $Y$?
Basically I want to know whether the sum being discrete uniform effectively forces the two component random variables to also be uniform on their respective domains.
To be a bit more precise:
...
- 121
11
votes
2
answers
491
views
How many random sieve operations to decimate the set {2,...,n}?
Let $S$ be the set of integers $\{2,3,4,\ldots,n\}$.
Consider the following process:
Select a random element $k \in S$.
Remove from $S$ every number divisible by $k$.
Repeat with this reduced $S$.
...
- 151k
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)...
- 7,320
11
votes
1
answer
1k
views
Smooth functions that resemble random walks
If the Riemann hypothesis holds, then the Mertens function $M(n)\equiv\sum_{x\leq n} \mu(n)$ behaves much like a 1D random walk. This includes the statements that
$M(n)$ changes sign infinitely often
...
11
votes
0
answers
307
views
Entropy, magnitude, diversity of finite metric spaces in number theory
I was reading the article by Tom Leinster, (Maximizing
diversity in biology and beyond, arXiv link), and find it very interesting.
Since I was searching for entropies of finite metric spaces I found
...
user6671
11
votes
0
answers
282
views
Reference request: a combinatoric result [closed]
When I tried to construct a counterexample in my research, I encountered the following result, which should be true.
Let $m=m(n)$ be a function that grows faster than $\sqrt n$, so $m(n) = \omega(\...
- 211
10
votes
2
answers
678
views
Irrational rotation - recurrence times
I consider the irrational rotation
$T_\alpha(x) = x + \alpha \text{ mod } 1$ for given irrational $\alpha \in [0,1]$. For a given open interval $A \subset [0,1]$ with length $|A|>0$, I consider the ...
- 103
10
votes
2
answers
926
views
Isomorphisms between spaces of test functions and sequence spaces
I am in the process of writing some self-contained notes on probability theory in spaces of distributions, for the purposes of statistical mechanics and quantum field theory. Perhaps the simplest ...
9
votes
6
answers
3k
views
Primes are pseudorandom?
I've been reading the wonderful slides by Terry Tao and thought about this question.
Primes appear to be quite random, and the formal statement should be that there are some characteristics of primes ...
- 15.1k
9
votes
2
answers
1k
views
Random pseudoprimes vs. primes
(Edit. What I called "pseudoprimes" are known as "Cramér random primes" in the literature,
of which I was unaware.)
Say that a set $S$ of natural numbers is a set of pseudoprimes if they
are (a) ...
- 151k
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
9
votes
1
answer
564
views
combinatorics on cyclic sequences
Given $m\geq 1$, let $I=(a_1,\ldots,a_{3m})$ be a sequence such that $I$ contains exactly $m$ zeros, $m$ ones, and $m$ twos.
Given $i=1,2$ and $j\leq 3m,k\leq m$ we can define $$U_{i,j}(k)=\text{...
- 167
8
votes
3
answers
3k
views
Is there any finitely-long sequence of digits which is not found in the digits of pi? [closed]
I know it's likely that, given a finite sequence of digits, one can find that sequence in the digits of pi, but is there a proof that this is possible for all finite sequences? Or is it just very ...
- 121
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
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
8
votes
2
answers
512
views
The average of reciprocal binomials
This question is motivated by the MO problem here. Perhaps it is not that difficult.
Question. Here is an cute formula.
$$\frac1n\sum_{k=0}^{n-1}\frac1{\binom{n-1}k}=\sum_{k=1}^n\frac1{k2^{n-k}}...
- 43.2k
8
votes
1
answer
171
views
On the existence of a particular type of finite measure on $\mathbb N$
Let $\mathbb N$ denote the set of all positive integers. Does there exist a countably additive measure $\mu : \mathcal P(\mathbb N) \to [0,\infty)$ such that $\mu(\mathbb N)<\infty$ and $\mu(\{nk: ...
- 1,209
8
votes
3
answers
847
views
Random linear recurrence relations
Problem
I am interested in the random recurrence relation of the form $x_{n+1}=\alpha x_n \pm \beta x_{n-1}$ where $\alpha$, $\beta$ are known constants and the $\pm$ sign is chosen with equal ...
- 3,217
8
votes
2
answers
537
views
Famous results about the value of a given limit assuming it exists
Chebyshev got famous showing that if the limit $l:=\lim_{x\to\infty}\frac{\pi(x)}{x/\log x}$ exists, then necessarily $l=1$, constituting a major breakthrough towards a proof of the famous prime ...
- 6,984
8
votes
2
answers
379
views
Sets whose elements are mutually "weakly" coprime?
Fix $n$ and $k$. I want a set $S\subseteq\{1,\ldots,n\}$ with the property that for every $x\in S$,
$$\mathrm{gcd}\bigg(x,\prod_{y\in S\setminus\{x\}}y\bigg)<\frac{x}{k}.$$
How small should a ...
- 7,633
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