All Questions
Tagged with pr.probability nt.number-theory
181 questions
3
votes
0
answers
420
views
(Expected) Size of smallest singular value of a Vandermonde matrix associated to roots of polynomial
Let $n,H$ two fixed positive integers.
Let $P\in\mathbb{Z}[X]$ a monic integral polynomial of height $H$ and degree $n$ taken uniformly at random (i.e. each of the $n$ free coefficients of $P$ is ...
- 313
2
votes
1
answer
479
views
Small geometric progression modulo N
An problem related to integer factorization using the General Number Field Sieve is the following:
Let $N$ be a composite. Must there exist a 5-term geometric progression $\lbrace a_0,a_1,a_2,a_3,...
- 39.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 $\...
- 7,193
4
votes
1
answer
386
views
Existence of normal number except random numbers
For normality, see https://en.wikipedia.org/wiki/Normal_number. For random number/sequence, see https://en.wikipedia.org/wiki/Algorithmically_random_sequence.
Now, is there any number that is normal ...
- 66.3k
2
votes
0
answers
88
views
Example of action of an infinitely countable group that has important ergodic/statistical property?
I work in probability and I am looking for an important example of action of an amenable countable group in other areas of math for which the (pointwise) ergodic theorem is actually quite important. ...
- 1,583
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) ...
CommunityBot
- 1
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)}{\...
CommunityBot
- 1
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}}...
CommunityBot
- 1
1
vote
2
answers
191
views
On non-singularity of integer matrices with bounded entries
Given $B>0$ and $n\in\Bbb N$ what is the probability that a given $n\times n$ integer matrix with all entries bound by absolute value $<B$ is non-singular? I am looking for precise scaling.
- 96.4k
2
votes
2
answers
370
views
Link between Irreducible Factors and Prime Factors (or Cycles of a Permutation)
In "Anatomy of Integers and Permutations", http://www.dms.umontreal.ca/~andrew/PDF/Anatomy.pdf, Granville gives a calibration of cycles of a permutation and prime factors of an integer. "We know ...
- 118k
3
votes
2
answers
411
views
When are "normal" functions normal?
I expected that the fractional part of f(n), n being an integer, would be distributed uniformly over [0,1] (for positive functions - otherwise take [-1,1]) for any run-of-the-mill function, except ...
- 54.2k
1
vote
0
answers
382
views
Probability that two integers selected from a fixed interval are relatively prime [closed]
I found the answer to a very similar question already asked here on mathoverflow: what is the probability that two natural numbers are relatively prime? The answer given in the link below was $\frac{6}...
CommunityBot
- 1
2
votes
1
answer
216
views
Ask for a special function related to the error function
I am wondering whether anyone knows the following integration has a named special function or a reference
$$
F_{a,b}(z) :=\frac{2}{\sqrt{\pi}} \int_0^z \text{erf}(a+b y)\: e^{-y^2} \text{d}y
$$
for ...
- 1,649
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,694
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{...
- 10.7k
7
votes
0
answers
267
views
Can primes be (almost) random sequence in von Mises sense?
Random models for primes (such as Cramer's model) have been extensively used for informal justification of various conjectures involving primes. It is crucial to understand in what sense sequence of ...
- 7,182
2
votes
0
answers
299
views
A weighted ergodic average
According to my simulations, it looks like the number of times that the $N$ first iterates $u_0$, $\ldots$, $u_{N-1}$ of the sequence $(u_n)$ defined here meets an interval $I$ is close to $N|I|$ ...
CommunityBot
- 1
2
votes
0
answers
72
views
Sampling efficiently conditioned on linear constraints modulo both $\mathbb{F}_p$ and $\mathbb{F}_2$
Given a prime $p$ and positive integer $t \ll \log p$ (say $t = \sqrt{\log p}$), is there an algorithm that is polynomial time in $\log p$ to sample uniform $X, Y \in \mathbb{F}_p$ conditioned on the ...
- 305
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$.
...
- 5,781
4
votes
1
answer
2k
views
Does Borel's proof for existence of normal numbers make an essential use of axiom of choice?
A normal number is a real number whose infinite sequence of digits in every base $b$ is distributed uniformly in the sense that each of the $b$ digit values has the same natural density $\frac{1}{b}$, ...
7
votes
1
answer
178
views
A case of nested central limits
Consider the random variable $S=(s_0, \dots ,s_{N-1})$, a sequence of signs uniformly distributed on the hypercube $\{-1,1\}^N$. We are interested in $N$ large and prime. The Fourier transform $\hat{S}...
- 1,085
7
votes
2
answers
321
views
Random suborbits of a rotation
Let $u_n = x + n\alpha \pmod 1$ with $\alpha$ irrational. We know that $(u_n)_{n \geq 0}$ is dense in $\mathbb{R}/\mathbb{Z}$ (equivalently $(u_n)_{n \geq 0}$ visits every open interval infinitely ...
- 2,135
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(\...
CommunityBot
- 1
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 ...
- 43.7k
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:...
CommunityBot
- 1
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 ...
- 19.6k
1
vote
2
answers
513
views
Primes as uncorrelated random variables [closed]
The heuristic justification section of the Wikipedia article about Goldbach's conjecture says that the argument that suggests that
the number of twin primes below $x$ should be roughly $\dfrac{x}{\...
- 24.8k
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}$ ...
CommunityBot
- 1
1
vote
0
answers
72
views
Question regarding a theorem of Erdos and Renyi on $B_2(g)$ sequence
Let $S \subset \mathbb{N}$. We say $S$ is of type $B_2(g)$ if the number of representation
of the form $n = s_1 + s_2 \ (s_1 \leq s_2)$ is bounded by $g$ for every $n \in \mathbb{N}$.
Let $S(n)$ be ...
- 579
2
votes
0
answers
192
views
A question related to metric Diophantine approximation
In metric Diophantine approximation you are often interested in finding conditions on $(\phi(q))_{q \geq 1}$ which guarantee that
$$
\left| \alpha - \frac{p}{q} \right| < \frac{\phi(q)}{q}
$$
has ...
- 2,207
2
votes
0
answers
970
views
Is the stationary distribution of this Markov chain uniform?
First, a little bit of background: Since 2012, Canada has decided to phase out the penny for its coinage system. Product prices may still use arbitrary cents, especially since prices do not typically ...
- 3,587
5
votes
2
answers
833
views
A central limit theorem for a trigonometric series involving primes
In some recent work I found I needed to prove a central limit theorem for
the interesting series:
$\sum_{n=1}^\infty \cos (u \log p_n) $
where u is a random variable uniform on the interval $[0,2\...
- 405
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$ ...
CommunityBot
- 1
2
votes
1
answer
261
views
Does the set of automorphisms of a cyclic group exhibit some sense of randomness?
I prefer to proceed with a concrete example if I may. I appreciate that the answer might well be better explained with group theory, geometry and/or notions from probability theory, which I welcome.
...
- 2,480
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=...
CommunityBot
- 1
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
1
vote
0
answers
233
views
Mellin transform of time-shifted function
The Mellin transform of a function $f(x)$ can be written as
$$
\mathcal M[f(x);z]=\int_0^\infty f(x)x^{z-1} dx
$$
Is there a simple expression for the Mellin transform of the function $f(x-x_0)$? ...
- 385
5
votes
3
answers
938
views
Analogy between Integers and Permutations
I am reading Andrew Granville's Anatomy of Integers and Permutations where it is argued the factorization of a permutation into disjoint cycles is analogous to the factorization of a number into prime ...
- 456
2
votes
1
answer
291
views
Prime Divisors of the $x \mapsto 2x+1$ Recursion
The Cohen-Lenstra statistics describe how often a prime divides the class number of quadratic number field $\mathbb{Q}[\sqrt{d}]$
$$ \mathbb{P}\big[h(d) \not\equiv 0\; (\mod p) \big] = \prod_{k \geq ...
CommunityBot
- 1
8
votes
0
answers
553
views
Hasse-Weil Bound and Chebyshev Inequality
I was reading about the Hasse-Weil bound for the number of points in on a curve over the finite field $\mathbb{F}_q$.
$$ \big| |C(\mathbb{F}_q)| - (q+1) \big| \leq 2g \sqrt{q} $$
However, this ...
- 22.8k
2
votes
0
answers
146
views
Odds of projections of a point not on the hyperplane
Let $\mathcal{L}=\{\Bbb x\in\Bbb R^n:x_1+x_2+\dots+x_n=0\}$ be a specific hyperplane.
Let a projection of $c\in\Bbb R^n$ be $p(c)=[p_1,p_2,\dots,p_n]$ where $p_i\neq c_i\implies p_i=0$.
Let $\...
- 13.9k
4
votes
0
answers
1k
views
Matula-Goebel ordering of rooted trees intrinsic?
I was somewhat recently introduced to the Matula-Goebel bijection between rooted trees and natural numbers. (nicely illustrated here http://keithbriggs.info/matula.html) Looking through them, I ...
- 3,587
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 ...
- 43.7k
2
votes
0
answers
238
views
Fractional Derivatives [closed]
How far these Theories of "Fractional Derivatives" be rigorized ? I have few books and references on Fractional Differential Equations etc (mainly they stress on Applied Mathematics parts and similar ...
CommunityBot
- 1
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 ...
- 4,679
1
vote
2
answers
1k
views
Sum of digits iterated
Original version.
I believe that it is an elementary question, already discussed somewhere. But I just have no idea of how to start it properly. Take a positive integer $n=n_1$ and compute its sum of ...
2
votes
2
answers
331
views
what's the best way to characterise the distribution of prime elements in simple perfect squared squares
DEFINITIONS: A squared rectangle is a rectangle dissected into a finite number, two or more, of squares, called the elements of the dissection. If no two of these squares have the same size the ...
2
votes
0
answers
202
views
Bunimovich stadium bouncing ball
http://terrytao.wordpress.com/2008/07/07/hassells-proof-of-scarring-for-the-bunimovich-stadium/
I cannot relate how the eigenfunctions normalizaed correspond to the probabality distribution of the ...
- 163
7
votes
2
answers
639
views
Is there an algebraically normal function from $\mathbb{Z}^{n}$ to $\{ 0 , 1\}$?
Definition: Let $h$ be a polynomial in $n$ variables, then :
$\gamma(h,r,R):=\{ v \in \mathbb{Z}^{n} : \vert h(v) \vert \leq r, \Vert v \Vert < R \}$
Let $\omega : \mathbb{Z}^{n} \to \{ 0 , 1\}$...
CommunityBot
- 1
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 ...
CommunityBot
- 1