6
$\begingroup$

Let remainder $r$ be defined as $$ r = n - pq $$ where $n \in \mathbb{N}$ is the dividend , $q \in \mathbb{R}$ is the divisor, and $p = \mathrm{floor}(n/q)$.

I calculated the remainders by dividing by $\pi$ for $1,2,\dots,100000$, then I got the reminders seem to follow a uniform distribution on $[0,\pi)$.

histogram of remainder

When the divisor is rational, it's obvious that the remainder is limited to some certain values.

When it comes to a irrational divisor, it makes intuitive sense to me that the remainders can have any values on $[0,q)$, and follow a uniform distribution. However, I have no idea how to prove this.

EDIT: Added histogram.

$\endgroup$
9
  • $\begingroup$ Hint: look at the "truncated" problem, where you require that $n≤K$. If $K$ happens to be a multiple of q, then your claim is clear (for the truncated problem). Otherwise it is false but only because of the small piece between $\left[\frac Kq\right] q$ and $K$. The significance of that little piece goes to 0 as $K\rightarrow \infty$ $\endgroup$
    – lulu
    Aug 1, 2015 at 14:53
  • $\begingroup$ @lulu Is that sufficient to show that the if we bin the range of remainders into equal sized bins (any number of bins, say $M$), then the ratio of counts in any two bins goes to $1$ as $K \to \infty$? I.e., in particular, the limit always exists and is $1$? $\endgroup$ Aug 1, 2015 at 14:57
  • $\begingroup$ Yes. Again, this is clear if $K$ happens to be a multiple of $q$, so the only problem is that your bins may intersect that little stub piece differently. The probability of that goes to $0$. $\endgroup$
    – lulu
    Aug 1, 2015 at 15:02
  • $\begingroup$ @lulu: I don't see where you made use of the irrationality of $q$. If your argument is correct, why doesn't it work for rational $q$? $\endgroup$
    – joriki
    Aug 1, 2015 at 15:04
  • $\begingroup$ @user2566092 I phrased that poorly. The problem is that, if your $n$ happens to fall in the stub piece then the probability that $n$ lies in one or the other of your bins might be unequal. But the probability of $n$ falling into the stub piece goes to $0$. $\endgroup$
    – lulu
    Aug 1, 2015 at 15:04

3 Answers 3

7
$\begingroup$

Dividing your formula by $q=\pi$ gives $$ n \cdot \frac{1}{\pi} = p + \frac{r}{\pi} , $$ so $p$ is the integer part, and $\frac{r}{\pi}$ is the fractional part, of $n \cdot \frac{1}{\pi}$. As $n$ runs through the integers, this fractional part $\frac{r}{\pi}$ is uniformly distributed on $[0,1)$ by Weyl's equidistribution theorem, since $\frac{1}{\pi}$ is irrational. Hence $r$ is uniformly distributed on $[0,\pi)$.

$\endgroup$
4
  • $\begingroup$ I would have to do more reading to figure out what Weyl's theorem's "uniformly distributed" means for a countable set of sequence terms, especially since it seems that reordering the terms in a weird way will make the distribution NOT uniform. Do you happen to know, does it mean that for any finite partition of the target interval into subintervals, that if the multiples are taken in order then the proportion of multiples in each subinterval converges to be proportional to the length of the subinverval? $\endgroup$ Aug 1, 2015 at 16:20
  • $\begingroup$ Yes, if the sequence of remainders is $(r_n)_1^\infty$, then the quantity "$(1/n) \times$ (the number of elements among $r_1,\dots,r_n$ that fall in the interval $I \subset [0,1)$" converges (as $n \to \infty$) to the length of the interval $I$. $\endgroup$ Aug 1, 2015 at 18:30
  • $\begingroup$ Take a look at Kar's "Weyl's Equidistribution Theorem", Resonance 8:5, 30-37 (may 2003), e.g. here for an approachable discussion. $\endgroup$
    – vonbrand
    Aug 1, 2015 at 19:13
  • $\begingroup$ I found that uploaded to Kar's website. This seems too general for my question, but it's very interesting. I also found another explanation for my pariqular question, which is written in my mother tongue, Japanese. $\endgroup$
    – pandaman
    Aug 2, 2015 at 15:01
1
$\begingroup$

As said in the answer of @HansLundmark this is Weyl's equidistribution theorem. It is an application of the ergodic theorem combined with the theorem that an irrational rotation of the circle is ergodic, and here's some details of how to reduce it to those two theorems.

Consider the unit circle $S^1$ in the complex plane. Given $q \in \mathbb{R}$, consider the function which rotates the circle $S^1$ through the angle $\frac{2 \pi}{q}$: $$R(z) = e^{2 \pi i / q} z $$ Define the iterates of this function by induction to be $$R^n(z) = R(R^{n-1}(z)) $$ Your remainder function $r(n) \in [0,q)$ is the unique function such that $$R^n(1) = e^{2 \pi i \, r(n)/q} $$ This sequence $R^n(1)$ is the "orbit" of $1=1+0i$ under the action of the function $R(z)$.

So your question comes down to asking: Why is the subset $\{R(x), R^2(x),\ldots,R^n(x)\}$ equally distributed in the circle as $n \to +\infty$?

Now let's bring in the ergodic theory.

Let $\mu$ denote the Borel measure on $S^1$ which assigns to an interval of angle $\alpha$ a measure of $\alpha/2\pi$. The theorem referred to above says that since $\frac{1}{q}$ is irrational, the transformation $R$ is ergodic with respect to $\mu$, and that means: for all $\mu$-measurable subsets $A \subset S^1$, if $R(A)=A$ then $\mu(A)=0$ or $1$.

Next we apply the Ergodic Theorem which, using that $R$ is ergodic with respect to $\mu$, says: For every $\mu$-integrable function $f : S^1 \to \mathbb{R}$ and for $\mu$-almost every $x \in S^1$ we have $$\lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n f(R^i(x)) = \int_{S^1} f \, d\mu $$ So finally we can use this to see why an orbit is equally distributed. Take an angular interval $A \subset S^1$ of angle $\alpha$, and let $\chi_A$ be the characteristic function of $A$. The expression $\frac{1}{n} \sum_{i=1}^n \chi_A(R^i(x))$ (under the limit sign on the left hand side) is simply the proportion of the points in the set $\{R(x), R^2(x),\ldots,R^n(x)\}$ which lie in $A$. What "uniformly distributed" should mean is that limit of this proportion as $n \to \infty$ (the left hand side) should be equal to $\alpha/2\pi=\mu(A)=\int_{A} d\mu = \int_{S^1} \chi_A$ (the right hand side). And they are indeed equal, that is exactly what the Ergodic Theorem says.

$\endgroup$
1
  • $\begingroup$ How do you know that the particular $x$ that you start with here is among the almost every $x$ that the ergodic theorem gives you? $\endgroup$ Aug 3, 2015 at 7:52
0
$\begingroup$

Ok, I'm sure I am making an error but I can't spot it. I understand (because I just looked it up) that this is typically proven by ergodic methods but it still seems elementary to me. I expect I am making a blunder and would appreciate having someone show me where.

We wish to show that if two intervals within $[0,q]$ have the same length then the remainder is equally likely to be in either of them.

Suppose the desired interval has length $\Delta$. Since $q$ is irrational we know that, given any positive $\Delta$ we can find an integer $m$ with $(mq)$ less than $\Delta$ (where $(x)$ denotes the remainder $x\;mod (q)$. More generally, if $N$ is a (large) integer we can find an integer $m(N)$ such that $(m(N)q)<\frac{\Delta}{N}$. We now partition the natural numbers by congruence classes mod (m(N)). Take any interval $[a,b]$ of length $\Delta$. We count the number of congruence classes $m_i\;\;mod(m(N))$ such that $(m_i q)\in[a,b]$ and get $\left[\frac{a}{(m(N)q)}\right]-\left[\frac{b}{(m(N)q)}\right]$. But this is always within $2$ of $\frac{a-b}{(m(N)q)}$ and as $N\rightarrow\infty$ we see independence of the placement of $a$ and $b$.

$\endgroup$
7
  • $\begingroup$ How did you arrrive at $\left[\frac{a}{(m(N)q)}\right]-\left[\frac{b}{(m(N)q)}\right]$? $\endgroup$
    – joriki
    Aug 1, 2015 at 16:38
  • $\begingroup$ @joriki searched for the smallest (and largest) congruence class that might fit in the interval. Did I screw up there? How embarrassing. Let me check. $\endgroup$
    – lulu
    Aug 1, 2015 at 16:42
  • $\begingroup$ I don't see how that's obvious. The values of $(m_iq)$ jump all over the place. It seems as if you're treating them as if they increase monotonically with $m_i$. $\endgroup$
    – joriki
    Aug 1, 2015 at 16:44
  • $\begingroup$ @joriki My "reasoning": if $m_i=i\;mod m(n)$ then $m_i=i +km(N)$ and $qm_i=q+km(N)q$ so $qmi=km(N)q \;modq$ . So, granted, this depends on the choice of k. I am definitely being hasty hence careless here. I understand that should mean I ought to stop, but I am intrigued. I feel confident that there is an elementary proof along these lines. I will persist. $\endgroup$
    – lulu
    Aug 1, 2015 at 17:06
  • $\begingroup$ @joriki This is (clearly) not my field...is it generally accepted that there is no elementary proof? I don't want to waste my time, but it seems to me that my "argument" is converging to a proof. $\endgroup$
    – lulu
    Aug 1, 2015 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.