6
votes
1answer
643 views

Probability that a positive integer is the euler phi function of another positive integer

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 ...
15
votes
0answers
412 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 ...
2
votes
1answer
221 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. ...
14
votes
3answers
933 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 ...
0
votes
0answers
77 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)$? ...
4
votes
3answers
575 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 ...
2
votes
1answer
199 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 ...
8
votes
0answers
193 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 ...
0
votes
0answers
95 views

Upper bound for $r_{0}(n)$ through probabilities

Assume Goldbach's conjecture. Then for every integer $n>1$ there exists a non negative integer $r$ such that both $n-r$ and $n+r$ are primes. For a given $N$, let's denote by $r_{0}(N)$ the ...
7
votes
2answers
278 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 ...
2
votes
0answers
133 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 ...
2
votes
0answers
139 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 ...
10
votes
3answers
640 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}$ ...
2
votes
2answers
226 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 ...
1
vote
0answers
147 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 ...
3
votes
2answers
593 views

Uniformly distributed sequence in $\mathbb{R}$

We say that a sequence $(x_n)_{n=1}^\infty \subseteq \mathbb{R}$ is "uniformly distributed in $[a,b]$", with $a < b$, if $(x_n)_{n=1}^\infty \cap [a,b] \neq \varnothing$ and $$\lim_{N \to \infty} ...
7
votes
2answers
600 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 , ...
2
votes
0answers
410 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 ...
2
votes
0answers
153 views

Expected period of quadratic generator

I am interested in the mean period of a quadratic congruential generator. Let $X_{n+1} = \sum_{i=0}^2 a_i X_n^i \bmod m$ where the $a_i \in \mathbb{Z_m}$ are chosen uniformly at random and $m$ is a ...
6
votes
2answers
906 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 ...
1
vote
1answer
405 views

Probability of all combinations of k numbers among n being coprime

A simple argument shows that if we choose $n$ positive integers at random, the probability of their greatest common divisor being 1 is $1/ \zeta (n)$ (in the sense that if we choose the numbers among ...
2
votes
0answers
120 views

Are numbers $h_{r,s} = \sum_{k} P(r;s;k) \frac{1}{n^{2k}} \bigg(1-\frac{1}{n}\bigg)^{n-2k}$ irrational?

I asked this question on MSE and Mike Spivey gave an insightful answer. I decided to put it here nevertheless in case someone else gets interested. If this violates rules on MO, please let me know, ...
5
votes
2answers
1k views

What is a random number? (poll experiment) [closed]

Imagine the following experiment: you wait say at a subway exit, and ask everyone passing "please tell me a number" (positive integer, of course). You do this day after day, until you reach say 1M ...
32
votes
6answers
3k views

Geometric / physical / probabilistic interpretations of Riemann zeta(n>1)?

What are some physical, geometric, or probabilistic interpretations of the values of the Riemann zeta function at the positive integers greater than one? I've found some examples: 1) In MO-Q111339 ...
2
votes
3answers
807 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
votes
0answers
173 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 ...
8
votes
2answers
635 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) ...
1
vote
1answer
335 views

Probability that p and q are both prime provided q-p=2r

Hello, I would like to know whether there is a way, thanks to the prime number theorem, to give some kind of an equivalent of the probability that two positive integers $p$ and $q$ less than a given ...
1
vote
0answers
198 views

Calculating or estimating a combinatorial multivariate sum

Dear all, I'm currently looking at a problem in which the following combinatorial product emerges: $c(m_1,\dots,m_\lambda;n_1,\dots,n_\lambda)=\frac{m_1 ...
2
votes
0answers
191 views

Generator density in $\mathbb{Z}^*_p$

Hello, Consider the multiplicative group $(\mathbb{Z}/p)^*$ for a given prime $p$. We know that the number of generators in this group is $\phi(p-1)$ --- the Euleur totient function. The question is, ...
3
votes
1answer
300 views

accumulation points within Pisot numbers

Recall that Pisot numbers are algebraic integers greater than $1$, whose other Galois conjugates have modulus $<1$. The set of Pisot numbers is usually denoted $S$. It is known that $S$ is ...
2
votes
0answers
125 views

finding rank-3 tensors compatible with a rank-2 tensor projection

I am interested in the following problem: Consider a rank-3 symmetric tensor $\boldsymbol{\sigma}$ with $\sigma_{ijk}$ where $\sigma_{ijk}$ can be 0 or 1, and the symmetry is with respect to any ...
3
votes
2answers
395 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 ...
1
vote
0answers
283 views

What is the mean-value of a particular exponential sum related to the non-trivial zeros of Riemann's zeta function?

This question arose from an earlier one and the MO user's useful answers there: What are the values of the derivative of Riemann's zeta function at the known non-trivial zeros? (which is not a ...
0
votes
1answer
294 views

Lower bounds for partial sums of multiplicative functions

The motivation for this enquiry is to understand something about the impact of multiplicativity for $f:\mathbb{N}\rightarrow\mathbb{C}$ on the conditional convergence of Dirichlet series ...
1
vote
0answers
216 views

A probabilistic approach of (a weaker form of) Goldbach's conjecture

Hello, this message follows on from About Goldbach's conjecture and aims at modelling the quantity $N_{2}(n)$ by a random variable. Let $n$ be a fixed natural number and let's define for every ...
21
votes
2answers
898 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 ...
6
votes
0answers
534 views

Is there a probabilistic interpretation of Dedekind zeta functions?

Reading the interesting paper Honest Bernoulli excursions by Smith and Diaconis motivated the question whether probabilistic interpretations for general Dedekind zeta functions are known. In the ...
12
votes
4answers
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 ...
5
votes
2answers
408 views

Intrinsically measurable subsets of amenable semigroups.

This question is related to the one in http://mathoverflow.net/questions/65322/the-structure-of-certain-maximal-sets-of-means-into-amenable-semigroups. I open a different topic because they can be ...
3
votes
1answer
634 views

Special case of Duffin-Schaeffer conjecture

The Duffin-Schaeffer conjecture is an old conjecture in metric number theory which has withstood attempts to solve it for about 70 years. The statement can be found here: ...
0
votes
3answers
235 views

How can we pave the multiplicative semigroup $(\mathbb N,\cdot)$?

Let $(S,\cdot)$ be a semigroup and $W\subseteq S$ be a subset. Let me call $W$ "tile" if the following property is satisfied: there exist $s_1,...s_k\in S$ such that the sets $s_i\cdot W$ are pairwise ...
3
votes
1answer
679 views

Self Avoiding Walk Enumerations

Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic ...
18
votes
3answers
773 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 ...
52
votes
3answers
2k 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$ ...
0
votes
1answer
775 views

Generalizations of a product formula for the gamma function

Hello and Happy holidays. I am interested in generalizations of the following product formula for the gamma function $\Gamma(z)= \int_{0}^{\infty} t^{z-1}e^{-t}dt$ when $n \geq 2$: \begin{align} ...
0
votes
0answers
276 views

Estimating a multinomial sum

I have the following sum \begin{equation} \sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda} ...
21
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]| ...
2
votes
7answers
2k views

How to tell if two random polynomials are identical

Let t be a positive real number. Let P(x) and Q(x) be two random polynomials with integer coefficients. If P(t) = Q(t), then what is the probability that P(x) is not identical to Q(x)? Will it make a ...
7
votes
3answers
492 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 ...